w****x
发帖数: 2483 | 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的不就得了？ | t*********7
发帖数: 255 | 2 只有你的出发点这个时候才是0,其他全部是INFINITY | i******e
发帖数: 273 | 3 如果节点A到节点B的最短路径经过节点C,那么这条最短路径上从A至C之间的子路径一定
是从节点A到节点C的最短路径。也就是说，从A到B的最短路径是建立在从A到C的最短路
径基础上的，这是为什么每次总是从unfinished节点集合中找当前距离源点最近的节点
的原因。
节点集合应该放到一个按节点和源点距离排序的min priority_queue中。但是由于每个
节点对源点距离是动态变化的，STL和Java的Priority_queue似乎不能处理这种情况，
那位大牛说说应该怎么解决？ |
|
