環状の2つの所与のノード間の最短経路は、環状の2つの所与のノード間の最短経路を取得するためにどのように重み付けグラフ

Question

に向けノードのリストとして重み付きグラフを監督しましたか？

Answer 1

私はダイクストラのアルゴリズムはあなたが探しているものだと思う：

• http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

あなたがタイプノードの追加マップを（使用する必要がありますノードのリストとして最短パスを取得するには - >ノード）を使用して、ノードの先行ノードを追跡します。

たちは空のマップとB.

スタートを超えるCまでの最短経路を見つけると仮定します。ノードAからノードBまでの暫定距離を更新するときには、関係B-> Aをマップに挿入します（これは、AがBの前身であることを意味します）。 Bまでの距離がさらに短い場合は、マップエントリを上書きします。 > AとC - - あなたのアルゴリズムでは、あなたのマップを終えた

は、エントリBが含まれています> B.今あなたが戻っマップを通してあなたの方法をトレースし、リストを作成することができます。