5.4 Shortest-path problem Let G=(v,E, w) be a weighted connected simple graph, w is a function from edges set E to position real numbers set. We denoted the weighted of edge i, by w(i,j, and w(i,j)=+oo when JEE 4 Definition 21: Let the length of a path p in a weighted graph G=(V,E, w) be the sum of the weights of the edges of this path. We denoted by w(p). The distance between two vertices u and v is the length of a shortest path between u and v, we denoted by d(u, v). u=y min w(p)l pis a path between u and v, there is a path between u and v P
5.4 Shortest-path problem ❖ Let G=(V,E,w) be a weighted connected simple graph, w is a function from edges set E to position real numbers set. We denoted the weighted of edge {i,j} by w(i,j), and w(i,j)=+ when {i,j}E ❖ Definition 21: Let the length of a path p in a weighted graph G =(V,E,w) be the sum of the weights of the edges of this path. We denoted by w(p). The distance between two vertices u and v is the length of a shortest path between u and v, we denoted by d(u,v). = = w p p is a path between u and v there is a path between u and v u v d u v p min { ( )| } 0 ( , )
今 Dijkstra’ s algorithm( E W.Dijkstra) .o Let G=(V,E, w) and VEn where W>0. Suppose that s is a nonempty subset of Vand y∈S.LetT=Vs Example: Suppose that (u. s a shortest path between u andv。 Then(u,v,v",v)is a L, shortest path between u and v
❖ Dijkstra’s algorithm (E.W.Dijkstra) ❖ Let G=(V,E,w) and |V|=n where w>0. Suppose that S is a nonempty subset of V and v1S. Let T=V-S. Example: Suppose that (u,v',v'',v''',v) is a shortest path between u and v. Then (u,v',v'',v''') is a shortest path between u and v
o Let VET. l(v be the length of a shortest path from vI to v containing only vertices in s
❖ Let vT. l(v) be the length of a shortest path from v1 to v containing only vertices in S
6 7 2 Example: S=a, bj, 3 5 2T={c,d,e,2 lc a-c: ac 4 a.b.c 3 l(c)=3。 (e)= be 6 令a,b,C,e4,l(e)=4?× Note: l(v) is the length of a shortest path from vI to v containing only vertices in S 令le)=6,l(d)=8 (2)=00
❖ l(e)=? ❖ a,b,e 6; ❖ a,b,c,e 4, l(e)=4?。 ❖ Note:l(v) is the length of a shortest path from v1 to v containing only vertices in S. ❖ l(e)=6, l(d)=8 ❖ l(z)=。 Example ： S={a,b}, T={c,d,e,z} l(c)： a→c：a,c 4 a,b,c 3, l(c)=3
令l(C)=3,l(e)=6,l(d)=8,l(z)=∞o o minverl(v=lc=3 is the length of a shortest path from a to c. 8 Theorem 5.12: Suppose that mineT l(v)) l(V). Then the length of the shortest path from v, to v'is /(v)
❖ l(c)=3，l(e)=6, l(d)=8, l(z)=。 ❖ minvT {l(v)}=l(c)=3 is the length of a shortest path from a to c. ❖ Theorem 5.12：Suppose that minvT {l(v)}= l(v'). Then the length of the shortest path from v1 to v' is l (v')