修改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算法得到最短路徑兩個節點

回答

相關問題