修改Dijkstra的算法以打印最短路徑中的節點

我想知道如何修改這個函數來保存節點的最短路徑。這是從我的教科書小修改。修改Dijkstra的算法以打印最短路徑中的節點

template <class vType, int size> 
void weightedGraphType<vType, size>::shortestPath(vType vertex) { 
int i, j; 
double minWeight; 

for (j = 0; j < gSize; j++) { 
    smallestWeight[j] = weights[vertex][j]; 
} 

bool weightFound[size]; 

for (j = 0; j < gSize; j++) { 
    weightFound[j] = false; 
} 

for (i = 0; i < gSize; i++) { 
    int v; 
    cout << vertex << " to " << i << endl; 
    minWeight = INFINITY; 

    for (j = 0; j < gSize; j++) { 
     if (!weightFound[j]) { 
      if (smallestWeight[j] < minWeight) { 
       v = j; 
       minWeight = smallestWeight[v]; 
      } 
     } 
    } 

    weightFound[v] = true; 

    for (j = 0; j < gSize; j++) { 
     if (!weightFound[j]) { 
      if (minWeight + weights[v][j] < smallestWeight[j]) { 
       smallestWeight[j] = minWeight + weights[v][j]; 
      } 
     } 
    } 
} //end for 
} //end shortestPath

來源

2011-03-16 s00pcan

跟蹤包括最短路徑的節點，並打印在最後。你在某個特定部分遇到問題嗎？ –

主循環內的第一個for循環找到權重最低的第二個節點。下一個循環找到從第二個節點到目標節點的路徑。如果每次使用新值設置最小權重時只保存該值，那麼對於不是最短的路徑，其中會有額外的值。我的問題是，如何保存最短路徑中的節點列表，忽略其他路徑？如果這是一個遞歸算法，它會更清晰。 – s00pcan

這裏有一個很重要的提示：從路徑的盡頭開始，向後工作。 –

這裏有一個提示：對於每個節點，你知道你發現達到它的最小重量。你也可以知道到達這個節點的「最短路徑」來自哪裏，在你打這個節點之前。

來源

2011-03-16 19:38:24 dfan

我需要更多的解釋才能理解我需要在這裏做什麼。 – s00pcan

圖中有一個額外的'我來自'字段，當您找到節點的最短路徑時填寫 – sp2danny

-2

這樣做的一種方法是引入一個額外的循環，在所有節點上迭代算法，並且使用距離數組可以存儲「via node」元素。一旦你有從每個節點計算到其他節點的最短路徑，你所要做的就是跟隨你存儲的「via node」值。順便說一句，就效率而言，這個算法很糟糕，它是O（n^3）。

來源

2011-10-07 04:39:53 user959135

創建數組以記住目標節點的前驅，然後追溯。

這裏是充分執行改進Dijkstra的

#include<stdlib.h> 
#include<set> 
#include<iostream> 
#include<vector> 
#include<list> 
#include<limits.h> 
using namespace std; 
    struct myHeapcmp{ 
    bool operator()(const pair<int,int> &a,const pair<int,int>&b){ 
     return a.second<b.second; 
    } 

    }; 

typedef list<pair<int,int> > AdjList; 
typedef vector<AdjList> Graph; 
typedef multiset<pair<int,int>,myHeapcmp>MinHeap; 
vector<int> dijkstra(Graph g,int N,int s){ 
    vector<int>d(N,100); 
    vector<int> predecessor(N); 
    d[s] =0; 
    vector<int>p(N,-1); 
    vector<MinHeap::iterator>HeapPos(N); 
    MinHeap h; 
    for(int i=0;i<N;i++) 
    HeapPos[i] = h.insert(make_pair(i,d[i])); 
    MinHeap::iterator it; 
    while(h.size()>0){ 
    it = h.begin(); 
    int v = it->first; 

    h.erase(it); 
    AdjList::iterator it2; 
    for(it2=g[v].begin();it2!=g[v].end();it2++){ 
     int u = it2->first; 
     int w_uv= it2->second; 
     if(d[u]>w_uv+d[v]){ 
     d[u]= w_uv+d[v]; 
     predecessor[u] = v; 
     p[u]=v; h.erase(HeapPos[u]); 
     HeapPos[u]= h.insert(make_pair(u,d[u])); 
     } 

    } 
    } 
    for(int i = 0;i<N;i++){ 
     int node = i; 
     int pre = predecessor[i]; 
     cout<<i<<" :"; 
     while(pre!=s){ 
      cout<<pre<<" "; 
      node = pre; 
      pre = predecessor[node]; 
     } 
     cout<<s<<endl; 
    } 

return d; 
}

來源

2015-09-04 18:32:50 user2258408

修改Dijkstra的算法以打印最短路徑中的節點

回答

相關問題