上浒充通大学 SHANGHAI JLAO TONG UNIVERSITY Greedy Algorithm Example2: Dijkstra's Algorithm (Being Greedy with Care 漏 AUMAAMAAA SHANC 1日g
Greedy Algorithm Example2: Dijkstra's Algorithm (Being Greedy with Care)
上游充通大粤 SHANGHAI JLAO TONG UNIVERSITY Shortest Paths in a Graph PR I N C F T O 强 是 SFRNGDALE coUau shortest path from Princeton CS department to Einstein's house 1日g 12G
Shortest Paths in a Graph shortest path from Princeton CS department to Einstein's house
上海充通大学 Shortest Path Problem SHANGHAI JLAO TONG UNIVERSITY Shortest path network. Directed graph G=(V,E). Source s.destination t. Length (length of edge e. © Shortest path problem:find shortest directed path from s to t. t cost of path sum of edge costs in path 23- 3 9 s 18- Cost of path s-2-3-5-t 14 6 =9+23+2+16 30 4 19 =48. 15 5 5 6 20 16 44
13 Shortest Path Problem Shortest path network. • Directed graph G = (V, E). • Source s, destination t. • Length e = length of edge e. Shortest path problem: find shortest directed path from s to t. Cost of path s-2-3-5-t = 9 + 23 + 2 + 16 = 48. s 3 t 2 6 7 4 5 23 18 2 9 14 15 5 30 20 44 16 11 6 19 6 cost of path = sum of edge costs in path
上海充通大学 Dijkstra's Algorithm SHANGHAI JLAO TONG UNIVERSITY Dijkstra's algorithm. Maintain a set of explored nodes S for which we have determined the shortest path distance d(u)from s to u. Initialize S={s),d(s)=0. Repeatedly choose unexplored node v which minimizes π(v)= min d(u)+le, e=(u,v):u∈S add v to S,and set d(v)=(v). shortest path to some u in explored part,followed by a single edge (u,v) d(u)
14 Dijkstra's Algorithm Dijkstra's algorithm. • Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u. • Initialize S = { s }, d(s) = 0. • Repeatedly choose unexplored node v which minimizes add v to S, and set d(v) = (v). ( ) min ( ) , ( , ) : e e u v u S v = d u + = s v u d(u) S e shortest path to some u in explored part, followed by a single edge (u, v)
上海充通大学 Dijkstra's Algorithm SHANGHAI JLAO TONG UNIVERSITY Dijkstra's algorithm. Maintain a set of explored nodes S for which we have determined the shortest path distance d(u)from s to u. Initialize S={s),d(s)=0. Repeatedly choose unexplored node v which minimizes π(v)= min d(u)+le, e=(u,v):u∈S add v to S,and set d(v)=(v) shortest path to some u in explored part,followed by a single edge (u,v) Adjust S if v affects other elements in S(Being greedy with care). d(u)
15 Dijkstra's Algorithm Dijkstra's algorithm. • Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u. • Initialize S = { s }, d(s) = 0. • Repeatedly choose unexplored node v which minimizes add v to S, and set d(v) = (v) • Adjust S if v affects other elements in S (Being greedy with care). ( ) min ( ) , ( , ) : e e u v u S v = d u + = s v u d(u) shortest path to some u in explored part, followed by a single edge (u, v) S e