相互接続されたエッジ ( E) のリストがあります。ある頂点から別の頂点に接続する最短パスを見つけるにはどうすればよいですか?
最低共通祖先の使用を考えていますが、エッジには明確に定義されたルートがないため、解決策はうまくいかないと思います。
最短パスは、通過する頂点の最小数によって定義されます。
注: 2 つの頂点を接続するマルチパスが存在する可能性があるため、明らかに幅優先検索は機能しません。
15478 次
5 に答える
9
ダイクストラのアルゴリズムがこれを行います。
于 2009-11-02T05:35:58.253 に答える
8
ノードのすべてのペア間または 2 つの特定のノード間にパスが必要かどうかはわかりません。前者についてはすでに回答があったので、後者について説明します。
グラフに関する予備知識がない場合 (知っている場合は、A*などのヒューリスティック ベースの検索を使用できます)、幅優先検索を使用する必要があります。
于 2009-11-02T05:40:20.993 に答える
2
Floyd-Warshallアルゴリズムは問題の解決策として考えられますが、全ペア最短経路問題を解決する他の解決策もあります。
于 2009-11-02T06:50:10.770 に答える
1
Shortest path is defined by the minimum number of vertexes treversed
これは、エッジの最小数に 1 を加えたものと同じです。
標準の幅優先検索を使用でき、正常に機能します。2 つの頂点を接続する複数のパスがある場合は、そのうちの 1 つを保存するだけで、すべてのエッジの重みが 1 であるため、何の影響もありません。
于 2009-11-02T10:08:06.423 に答える
0
さらに2セント。networkxを見てください。必要なものに対してすでに実装されている興味深いアルゴリズムがあり、最適なものを選択できます。
于 2009-11-02T06:59:29.493 に答える