使用Dijkstra算法與unordered_map圖

Question

所以這我當前的代碼，我將發佈以下聲明頭...

// Using Dijkstra's 
int Graph::closeness(string v1, string v2){ 
int edgesTaken = 0; 
unordered_map<string, bool> visited; 
unordered_map<string, int> distances; 
string source = v1; // Starting node 
while(source != v2 && !visited[source]){ 
    // The node has been visited 
    visited[source] = 1; 
    // Set all initial distances to infinity 
    for(auto i = vertices.begin(); i != vertices.end(); i++){ 
     distances[i->first] = INT_MAX; 
    } 
    // Consider all neighbors and calculate distances from the current node 
    // & store them in the distances map 
    for(int i = 0; i < vertices[source].edges.size(); i++){ 
     string neighbor = vertices[source].edges[i].name;   
     distances[neighbor] = vertices[source].edges[i].weight; 
    } 
    // Find the neighbor with the least distance 
    int minDistance = INT_MAX; 
    string nodeWithMin; 
    for(auto i = distances.begin(); i != distances.end(); i++){ 
     int currDistance = i->second; 
     if(currDistance < minDistance){ 
      minDistance = currDistance; 
      nodeWithMin = i->first; 
     }  
    } 
    // There are no neighbors and the node hasn't been found yet 
    // then terminate the function and return -1. The nodes aren't connected 
    if(minDistance == INT_MAX) 
     return -1; 
    // Set source to the neighbor that has the shortest distance 
    source = nodeWithMin; 
    // Increment edgesTaken 
    edgesTaken++; 
    // clear the distances map to prepare for the next iteration 
    distances.clear(); 
} 
return edgesTaken; 
} 

聲明（這是一個無向圖）：

class Graph{ 
    private: 
      // This holds the connected name and the corresponding we 
      struct EdgeInfo{ 
        std::string name; 
        int weight; 
        EdgeInfo() { } 
        EdgeInfo(std::string n, int w) : name(n), weight(
      }; 

      // This will hold the data members of the vertices, inclu 
      struct VertexInfo{ 
        float value; 
        std::vector<EdgeInfo> edges; 
        VertexInfo() { } 
        VertexInfo(float v) : value(v) { } 
      }; 

      // A map is used so that the name is used as the index 
      std::unordered_map<std::string, VertexInfo> vertices; 

注意：請不要建議我更改標題聲明，我正在爲一個已經編寫了8個其他函數的項目做出貢獻，現在肯定爲時已晚，無法返回並更改任何內容，因爲所有其他函數都必須重寫

我目前得到不正確的輸出。該函數正確地處理0距離情況（但如果兩個頂點沒有連接，則函數應返回-1）。如果兩個節點是同一頂點離接近（「波士頓」，「波士頓」），則該函數將返回0。

實施例圖

在以下兩個頂點的接近程度左將在右邊：

Correct: 
Trenton -> Philadelphia: 2 
Binghamton -> San Francisco: -1 
Boston -> Boston: 0 
Palo Alto -> Boston: -1 

Output of my function: 
Trenton -> Philadelphia: 3 
Binghamton -> San Francisco: -1 
Boston -> Boston: 0 
Palo Alto -> Boston: 3 

我試圖複製Dijkstra的它究竟是如何描述的，但我得到不正確的讀數，我一直在努力，現在摸不着頭腦了一會兒 - >任何人都可以將我指向正確的方向嗎？

Answer 1

你的實現是錯誤的，只有偶然你得到「正確」的結果。

讓我們用手做一個例子。從特倫頓到費城。我使用城市的第一個字母作爲標籤。

First iteration 
visited = [(T, 1), (N, 0), (W, 0), (P, 0), (B, 0)] 
minDistance = 3; 
nodeWithMin = N; 
edgesTaken = 1 

second iteration 
visited = [(T, 1), (N, 1), (W, 0), (P, 0), (B, 0)] 
minDistance = 2; 
nodeWithMin = W; 
edgesTaken = 2 

third iteration 
visited = [(T, 1), (N, 1), (W, 1), (P, 0), (B, 0)] 
minDistance = 2; 
nodeWithMin = N; 
edgesTaken = 3; 

fourth iteration 
N is already 1 so we stop. Can you see the errors? 

傳統Dijkstras最短路徑算法與優先級隊列

dijkstra(graph, source) 
    weights is a map indexed by nodes with all weights = infinity 
    predecessor is a map indexed by nodes with all predecessors set to itself 
    unvisited is a priority queue containing all nodes 

    weights[source] = 0 
    unvisited.increase(source) 

    while unvisited is not empty 
     current = unvisited.pop(); 
     for each neighbour to current 
     if weights[current] + edge_weight(current, neighbour) < weights[neighbour] 
      weights[neighbour] = weights[current] + + edge_weight(current, neighbour) 
      unvisited.increase(neighbour) 
      predecessors[neighbour] = current 

    return (weights, predecessors) 

實現，您可以通過以下前人得到的路徑長度。

Answer 2

這個問題肯定不是問題的真正答案（因爲我沒有把你的方向指向你的實現），但是你是否想過只使用Boost Graph庫？

它歸結爲爲您的圖形結構編寫一個簡短的Traits類（因此不需要更改圖形定義/標題），並且至少對於這些基本算法而言，證明其運行穩定且正確。

我一直建議不要重新發明輪子尤其是當它涉及到的圖表和數字...

Answer 3

與帕洛阿爾託的問題 - >波士頓似乎是，該算法採用的路線Palo Alto -> San Fransisco -> Los Angeles -> San Fransisco（edgesTaken = 3），然後失敗，因爲聖弗朗西斯科已被訪問。