今 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 v1S. 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