利用Dijkstra算法求A到D的最短通路 B(2,A) C(o,-) B(2,A C(9,B) E(o,-） E(4,B) Fo,-） )AC QF(oo,-） D(o,-) D(0,-) G(6,A) H(o,） G6,A) Ho,-) D() p() 变量： c(i,j):从节点i到j链路代价 步骤： (初始状态下非相邻节点之间的 初始化 链路代价为无限大) 除了源节点外，所有节点都为临时节点 D(v):从源节点到节点V的当前 路径代价（节点的代价） 节点代价除了与源节点代价相邻的节点外，都为∞ p(v):从源到节点V的路径前序 从所有临时节点中找到一个节点代价最小的临时节点（标记紫 节点 色)，将之变成永久节点（当前节点）W 对此节点W的所有在临时节点集合中的邻节点(V) 节点标记：每一个节点使用 V(D(v),p(v))如：B(2,A)标记 如D()>D(wM+cw,),则重新标注此点，V(DwM+c(w,V),W) 2类节点： 否则，不重新标注 临时节点（红色）：还没有找到 严始一个新的循环 从源节点到此节点的最优路径 的节点 永久节点（绿色）：已经找到了 从源节点到此节点的最优路径 的节点
利用Dijkstra算法求A到D的最短通路 A B C E F G H D 2 2 1 6 4 2 7 3 2 2 3 A B(2,A) E(∞,-) G(6,A) C(∞,-) F(∞,-) H(∞,-) D(∞,-) A B(2,A) E(4,B) G(6,A) C(9,B) F(∞,-) H(∞,-) D(∞,-) 变量： c(i,j): 从节点i到j链路代价 (初始状态下非相邻节点之间的 链路代价为无限大) D(v): 从源节点到节点V的当前 路径代价(节点的代价) p(v): 从源到节点V的路径前序 节点 节点标记: 每一个节点使用 V(D(v),p(v)) 如：B(2,A)标记 2类节点: 临时节点(红色) :还没有找到 从源节点到此节点的最优路径 的节点 永久节点(绿色) :已经找到了 从源节点到此节点的最优路径 的节点 步骤： 初始化 除了源节点外,所有节点都为临时节点 节点代价除了与源节点代价相邻的节点外,都为∞ 从所有临时节点中找到一个节点代价最小的临时节点（标记紫 色）,将之变成永久节点(当前节点)w 对此节点w的所有在临时节点集合中的邻节点(V) 如 D(v)>D(w) + c(w,v), 则重新标注此点,V (D(w)+c(w,v), w) 否则，不重新标注 开始一个新的循环 D(v) p(v)
利用Dijkstra算法求A到D的最短通路 B(2,A) C(o,-) B(2,A) C(9,B) E(o,-） E(4,B) QF(oo,-） aF(o,-） D(0o,） D(0,-) H G6,A) H(o,-) G6,A) H(oo,-） B(2,A C9,B) B(2,A) C(9,B) B(2,A) C(9,B) E(4,B E4,B) E(4,B) F(6,E) F(6,E) F(6,E) D(0,-) D(o,) D(o,-） G(5,E) Ho,-) G(5,E) H9,G) G5,E) H(8,F) B(2,A) C(9,B) B(2.A C(9,B) B(2,A) C(9,B) E(4,B) E(4,B) E(4,B) F(6,E) F(6,E) F(6,E) D(10,H) D(10,D D(10,H G(5,E) H8,F) G5,E) H(8,F) G5,E) H(8,F) 最短通路为：A-B-E-F-H-D,权值为10
利用Dijkstra算法求A到D的最短通路 A B C E F G H D 2 2 1 6 4 2 7 3 2 2 3 A B(2,A) E(∞,-) G(6,A) C(∞,-) F(∞,-) H(∞,-) D(∞,-) A B(2,A) E(4,B) G(6,A) C(9,B) F(∞,-) H(∞,-) D(∞,-) A B(2,A) E(4,B) G(5,E) C(9,B) F(6,E) H(∞,-) D(∞,-) A B(2,A) E(4,B) G(5,E) C(9,B) F(6,E) H(9,G) D(∞,-) A B(2,A) E(4,B) G(5,E) C(9,B) F(6,E) H(8,F) D(∞,-) A B(2,A) E(4,B) G(5,E) C(9,B) F(6,E) H(8,F) D(10,H) A B(2,A) E(4,B) G(5,E) C(9,B) F(6,E) H(8,F) D(10,H) A B(2,A) E(4,B) G(5,E) C(9,B) F(6,E) H(8,F) D(10,H) 最短通路为：A-B-E-F-H-D，权值为10
利用Dijkstra算法求A到D的最短通路 B(2,A) C(0,-) B(2.A) C(9,B) E(o,-） E(4,B) QF(oo,-） aF(o,-） D(0o,) D(0,-) G(6,A) H(o,-) G6,A) H(,-) 步骤 D(B),p(B) D(G),p(G) D(E),p(E) D(C),p(C) D(F),P() D(H,p(H） D(D),p(D) 1 2,A 6,A 00,- 00, 00,- 00, 00, 2,A 6,A 4,B 9,B 00,- 00,- 0,- 5,E 4,B 9,B 6,E 00, 0, 5,E 96 6,E 8,F 00, 9,B 6,E 8,F 00, 9,B 8,F 10,H 9,B 10,H 8 10,H 最短通路为：A-B-E-F-H-D,权值为10
利用Dijkstra算法求A到D的最短通路 A B C E F G H D 2 2 1 6 4 2 7 3 2 2 3 A B(2,A) E(∞,-) G(6,A) C(∞,-) F(∞,-) H(∞,-) D(∞,-) A B(2,A) E(4,B) G(6,A) C(9,B) F(∞,-) H(∞,-) D(∞,-) 最短通路为：A-B-E-F-H-D，权值为10 步骤 D(B),p(B) D(G),p(G) D(E),p(E) D(C),p(C) D(F),p(F) D(H),p(H) D(D),p(D) 1 2,A 6,A ∞,- ∞,- ∞,- ∞,- ∞,- 2 2,A 6,A 4,B 9,B ∞,- ∞,- ∞,- 3 5,E 4,B 9,B 6,E ∞,- ∞,- 4 5,E 9,B 6,E 8,F ∞,- 5 9,B 6,E 8,F ∞,- 6 9,B 8,F 10,H 7 9,B 10,H 8 10,H