Использование алгоритма Дейкстры с 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 

Я попытался скопировать Дейкстры точно, как это описано, но я получаю неправильные показания, я пытался выяснить это на некоторое время теперь -> Может кто-то указать мне верное направление?

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 -> Бостон, кажется, что алгоритм принимает маршрут Palo Alto -> San Fransisco -> Los Angeles -> San Fransisco (edgesTaken = 3), а затем не удается выполнить условие, потому что Сан-Франциско уже был посещен.