Dijkstra 算法为什么优先populate当前最小dist的那个节点？# JobHunting - 待字闺中
w*x
1 楼
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph:
3 dist[v] := infinity ;
4
5 previous[v] := undefined ;
6
7
8 dist[source] := 0 ;
9 Q := the set of all nodes in Graph ;
10
11 while Q is not empty:
12 u := vertex in Q with smallest distance in dist[] ;
13 remove u from Q ;
14 if dist[u] = infinity:
15 break ;
16
17
18 for each neighbor v of u:
19
removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]:
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q;
25 return dist;
==================================
第12行为什么要去最小的？ 随便取一个不为infinity的不就得了？
2 for each vertex v in Graph:
3 dist[v] := infinity ;
4
5 previous[v] := undefined ;
6
7
8 dist[source] := 0 ;
9 Q := the set of all nodes in Graph ;
10
11 while Q is not empty:
12 u := vertex in Q with smallest distance in dist[] ;
13 remove u from Q ;
14 if dist[u] = infinity:
15 break ;
16
17
18 for each neighbor v of u:
19
removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]:
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q;
25 return dist;
==================================
第12行为什么要去最小的？ 随便取一个不为infinity的不就得了？