Dijkstra最短路徑與最小步驟

我需要實現一個程序，給定一個有向圖，在弧的正成本打印從x到y的最小代價和所有路徑的最小步數從x以最低的成本支付給y。我已經編寫了一個程序來做到這一點，但有時候需要一個沒有最小步數的路徑。這是我的代碼：Dijkstra最短路徑與最小步驟

#include <iostream> 
#include <vector> 
#include <queue> 
#include <climits> 

using namespace std; 

typedef pair<int, int> Warc; 
typedef vector<vector<Warc>> Wgraph; 

int dijkstra(const Wgraph& g, int x, int y, vector<int>& p) { 
    int n = g.size(); 
    vector<int> d(n, INT_MAX); //costs 
    p = vector<int>(n, -1); //parent of each vertice 
    d[x] =0; 
    vector<bool> S(n, false); 
    priority_queue<Warc, vector<Warc>, greater<Warc>> Q; 
    Q.push(Warc(0, x)); 
    while(not Q.empty()) { 
    int u = Q.top().second; 
    Q.pop(); 
    if(u == y) return d[u]; 
    if(not S[u]) { 
     S[u] = true; 
     for(Warc a : g[u]) { 
     int v = a.second; 
     int c = a.first; 
     if(d[v] > d[u] + c) { 
     d[v] = d[u] + c; 
     p[v] = u; 
     Q.push(Warc(d[v], v)); 
     } 
     } 
    } 
    } 
    return -1; 
} 

int main() { 
    int n; //# of vertices 
    while(cin >> n) { 
    int m; //# of arcs 
    cin >> m; 
    Wgraph g(n); 
    for(int i = 0; i<m; ++i) { 
     int u, v; 
     int c; 
     cin >> u >> v >> c; // arc: u->v with cost C 
     g[u].push_back(make_pair(c, v)); 
    } 
    int x, y; 
    cin >> x >> y; //origin and end 
    vector<int> p; //p[i]= parent of vertice i 
    int path = dijkstra(g, x, y, p); 
    if(path == -1) cout << "no path from " << x << " to " << y << endl; 
    else { 
     int s = 0; 
     int i = y; 
     while(i != x) { 
      ++s; 
      i = p[i]; 
     } 
     cout << "cost " << path-s << ", " << s << " step(s)" << endl; 
    } 
    } 
}

謝謝。

來源

2015-05-23 flapedriza

您是否嘗試過使用調試器來遍歷代碼？你是否試圖將它分解成更小的單位併爲它們編寫單元測試？ –

請注意，你的實現的複雜度將是'O（m log m）'，而它應該是'O（n log n）'（其中'n'是節點的數量，'m'是邊的數量）：您的優先級隊列在需要存儲節點時存儲邊。它還需要移動優先級隊列中的節點，這是'std :: priority_queue '不支持的操作。 –

您的算法使用它找到的第一條最短路徑。如果最小步驟部分中的最後一步很小，而更多步驟路徑中的最後一步更大，則更喜歡步驟路徑。 –

問題是你只考慮優先級隊列中的距離。因此，將使用隨機的最後一條邊來完成路徑，但只會考慮其中的一條。除了距離之外，還可以創建更高級的距離，其中考慮路徑的長度：主要重量將是距離，但對於相等距離，您會認爲邊距較短的路徑較短。

注意你的算法有錯誤的複雜性：它具有複雜O(m log m)代替O(n log n)（n爲節點的存在的邊數數，m），因爲你存儲邊緣的優先級隊列，而不是節點。 Dijstra的算法僅在存儲節點並根據需要在優先級隊列中調整它們的位置時纔有效 - 這是std::priority_queue<T>不支持的操作。

來源

2015-05-23 20:29:22

Dijkstra最短路徑與最小步驟

回答

相關問題