Diskjstra の代替として意図された BFS ベースのパス検索アルゴリズムを思いつきました (正直なところ、過去に他の人が思いついたのではないかと思いますが、オンラインのどこにも言及されていません)。実行時間を把握しようとしていますが、友人と議論していて、決定的な答えを出すことができませんでした. Go でのアルゴリズムの説明と実装へのリンクは次のとおりです: https://github.com/joshlf13/bfspath
実行時間は e + e^2 + e^4 + ... + e^2d であるという印象を受けています。ここで、e は頂点あたりのエッジの平均数、d は最終的な最短パスの距離です (O (e^2d))。問題は、これがアルゴリズムの結果に依存していることです。私の友人が指摘しているように、実行時間の考慮に含めるべきではありません。
私の推論は次のとおりです。BFS の各パスは、e の倍数と見なされる頂点の数を増やします。さらに、頂点が考慮されるたびに、それは e 操作です。したがって、各パスは v (パス内の頂点の数) x e です。v が 1 の場合、e の場合は e^2 など、v*e は e + e^2 + e^4 などです。
別のアプローチは、考慮されるエッジの数に関して実行時間を考慮することです。長さ N のエッジには、N 回の操作が必要です。したがって、エッジが E 個あり、平均エッジ長が N であるグラフの場合、それは O(N*E) です。ただし、これはアルゴリズムの操作中に考慮されるグラフの部分にのみ適用され、そのサブセットのサイズは、開始点と終了点の間の距離に比例してスケーリングされないため、O() の真の考慮が困難になります。 .
アイデア…？