Digital Map ver.1.06

何となく思っているだけなのですが、頂点数が多いときは、真面目に距離テーブルを作ってから普通に巡回セールスマンを解くより、必要に応じて距離テーブルを埋めていくようなやり方の方がいいような気がしています。
近似解法を全然知らないので適当に書いていますが、「距離テーブルから、ある頂点に近い順に頂点を取り出す」というのはDijkstra法の実行中に求められる訳で、工夫が必要かそうでないかも分からないのですが、例えば7と4との最短経路を求めずに、この黄色い巡回路が求められそうな気がします。双方向Dijkstraの複数頂点版みたいなイメージです。
でもオンメモリでやるなら、メモリを馬鹿食いしそうで厳しそうですね。

近い頂点から順に辿るだけのnearest neighborを実行するだけなら、ご指摘の通り距離テーブルは必要なくDijkstraで動的に距離テーブルを埋められるのですが、出来上がった巡回路に対して、2-Opt（簡単にいえば巡回路が短くなるようなら2本の枝を切って繫ぎ変える。）を適用するためには、距離テーブルすべてが埋まってなければ難しいと思います。

ちなみにnearest neighborだけだと、巡回路が交差したり、最後に巡回するルートが長くなってしまうという問題があります。

今考えている実用的なのは、京都とかだと社寺間だけの距離を計算しておくとかですかね。