所以我看到了与此类似的问题,但并不完全是我正在寻找的问题。我需要修改 Dijkstra 算法以返回顶点 S(源)和顶点 X(目标)之间的最短路径。我想我已经知道该怎么做了,但我需要一些帮助。这是我修改过的伪代码。
1 function Dijkstra(Graph, source, destination):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 dist[source] := 0 ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
13 remove u from Q ;
14 if dist[u] = infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]: // Relax (u,v,a)
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return dist[destination];
代码取自维基百科并修改:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
这看起来正确吗?
最佳答案
Dijkstra 算法不需要修改,它是一个all-pairs 最短路径算法。似乎您正在尝试找到两个特定节点之间的最短路径 - Dijkstra 处理得很好。
如果您想要专门为未加权、无向图设计的东西,这就是您正在做的事情,我建议您做一个 BFS。
关于data-structures - 修改 Dijkstra 算法得到两个节点之间的最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13447163/