修改Dijkstra算法得到最短路径两个节点

所以，我已经看到了类似的问题，这但不是之间有很大正是我要找的。我需要修改Dijkstra算法以返回顶点S（源）和顶点X（目标）之间的最短路径。我想我已经想出了该做什么，但我想要一些帮助。这是我修改过的伪代码。修改Dijkstra算法得到最短路径两个节点

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

这是否看起来是正确的？

来源

2012-11-19 csnate

为什么你需要修改它？这正是它所做的。当您将所有边权重设置为1. –

这是我已经修改的代码。所以如果它的效果很好。 – csnate

此外，由于Dijkstra中的顶点选择是贪婪的，只要您获得“u = destination”，就可以打破循环。 –

Dijkstra算法并不需要进行修改，这是一个所有点对最短路径算法。看起来你正在试图找到两个特定节点之间的最短路径--Dijkstra处理这个问题。

如果你想要的东西，对不加权，无向图，这是什么好像你正在做的，我建议做一个BFS专门设计的。

来源

2012-11-19 05:52:11 adelbertc

什么？迪杰斯特拉不是所有的对。 – rosstex

找到从单个SOURCE开始的最短路径后，我们需要从DESTINATION开始回溯其前任，以打印路径。

Print-Path(G,s,v) 
{ 
    if(v==s) 
     print s; 
    else if (pi[v]==NULL)  
     print "no path from "+s+" to "+v; 
    else{ 
     Print-Path(G,s,pi[v]) 
     print v; 
    } 
}

以上验证码礼貌介绍算法，麻省理工学院出版社

来源

2012-11-19 06:03:22 Daniel

接近这一点的最好办法是想从每个可达节点回源，用V通常表示为路径条款。如您更新每个给定节点的距离，跟踪其在该路径上的直接后继到v。该节点是给定节点在最短距离到v树中的父节点。当你建立了父映射时，要找到从v到w的最短路径，按照相反的顺序构建路径：w，parent [w]，parent [parent [w]]，...

来源

2014-05-27 20:34:54

修改Dijkstra算法得到最短路径两个节点

回答

相关问题