algorithm - Dijkstra: 有向グラフの最短経路を見つける

Question

下の図に示す有向グラフを考えてみましょう。頂点 S と頂点 T の間には複数の最短経路があります。Dijstra の最短経路アルゴリズムによって報告されるのはどれですか? どの反復においても、頂点 v への最短パスは、v への厳密に短いパスが発見された場合にのみ更新されると仮定します。

私の答えは SBDT ですが、ソリューションでは SACET を提供していますが、理由がわかりません..

Answer 1

ダイクストラのアルゴリズムは、次のようにノードを選択します。

B(3) from S
A(4) from S
C(5) from A
E(6) from C
D(7) from S or B
G(8) from E
T(10) from D or E

したがって、への最短経路TはSBDT、SDTまたはSACETです。

しかし、"the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered"がE訪問Tされると、 の最短経路の前のノードが に設定されE、再度変更されることはありません。

したがって、答えはSACETです。

Answer 2

http://dracos.co.uk/maths/dijkstra/で実行して ください。答えは SDT です。理由: ノード S の後、その直近の近隣ノードが考慮されます。つまり、A(4)、D(7)、B(3) これらのノードの直近の近隣ノードが考慮されます。C は S の直近の隣接ノードではないため、ノード C が考慮される前に SDT(10) に到達します。 回答: SDT