最短経路問題における探索候補点集合 - その２。

道路ネットワークグラフ（USA-road-d.XXX.gr）では、探索候補点集合内にある要素数はかなり少ない。

画像は USA-road-d.NY.gr において、点 ID 1 から点 ID 64346 までの P2P 最短路において、どのようにデータ構造内の要素数が変化したのか示したものだが、この２点はある程度離れているにもかかわらず、800 要素以下である。全米データであっても多くて 8000 程度と、少ない。

最大要素数は知っていたのだが、どのように増減するかは見たことがなかったので、参考のために調べてみることにした。Excel では大きなデータを扱えないので、10 探索刻みにデータ構造内の要素数を調べてみた。

要素数をうまく予測できるかということも考えもしたが、この様にしてみるとかなり難しいそうである。