グラフ理論の問題

辺の重みはすべて正なので、ダイクストラ法で $a$ から各頂点への最短距離 $d(\cdot )$ を求める。

• はじめに $d(a)=0$ と確定する。$a$ に隣接する頂点の暫定距離は $b:4,c:2$。
• 暫定距離が最小の $c$ を $d(c)=2$ と確定する。$c$ から更新すると $b:\min (4,2+1)=3$、$d:2+8=10$、$e:2+10=12$。
• $b$ を $d(b)=3$ と確定する。$b$ から更新すると $d:\min (10,3+5)=8$。
• $d$ を $d(d)=8$ と確定する。$d$ から更新すると $e:\min (12,8+2)=10$、$f:8+6=14$。
• $e$ を $d(e)=10$ と確定する。$e$ から更新すると $f:\min (14,10+3)=13$、$g:10+7=17$。
• $f$ を $d(f)=13$ と確定する。$f$ から更新すると $g:\min (17,13+1)=14$。
• 最後に $g$ を $d(g)=14$ と確定する。

最短路は $a\to c\to b\to d\to e\to f\to g$ で、長さは $2+1+5+2+3+1=14$ である。

よって、求める最短路の長さは $14$ である。

ダイクストラ法で $a$ からの最短距離を求める。

$d(a)=0$。$a$ から: $d(b)\le 4$, $d(c)\le 2$。
最小の $c$（2）を確定: $b$ は $2+1=3<4$ で 3 に更新、$d$ は $2+8=10$、$e$ は $2+10=12$。
次に $b$（3）を確定: $d$ は $3+5=8<10$ で 8 に更新。
次に $d$（8）を確定: $e$ は $8+2=10<12$ で 10、$f$ は $8+6=14$。
次に $e$（10）を確定: $f$ は $10+3=13<14$ で 13、$g$ は $10+7=17$。
次に $f$（13）を確定: $g$ は $13+1=14<17$ で 14。
最後に $g=14$ が確定。

最短路は $a\to c\to b\to d\to e\to f\to g$ で、長さは $2+1+5+2+3+1=14$。
検算: 他の候補 $a\to c\to e\to g$ は $2+10+7=19$、$a\to c\to b\to d\to f\to g$ は $2+1+5+6+1=15$ で、いずれも 14 より大きい。