Using Dijkstra's algorithm with an unordered_map graph

Question

So this my current code, I will post the header declarations below...

// 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;
}

Declarations (This is an undirected graph) :

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;

NOTE: Please do not suggest that I change the header declarations, I am contributing to a project that has already had 8 other functions written and it's definitely too late to go back and change anything since every other function would then have to be rewritten

I'm currently getting incorrect output. The function is handling a 0 distance situation correctly however (If two vertices aren't connected then the function should return a -1). If the two nodes are the same vertex ex closeness("Boston", "Boston") then the function should return a 0.

Example graph

the closeness of the following two vertices on the left will be on the right:

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

I've tried to copy dijkstra's exactly how it is described, but I'm getting incorrect readings, I've been trying to figure this out for a while now -> Can anyone point me in the right direction?

Answer 1

Your implementation is wrong, and it is only by chance you get "correct" results.

Lets do one example by hand. From Trenton to Philadelphia. I use the first letter of the cities as labels.

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?

Traditionally Dijkstras shortest path algorithm is implemented with a priority queue

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)

And you can get the path length by following the predecessors.

Answer 2

This is most certainly not a real answer to the question (since I'm not pointing you in a direction regarding your implementation), but did you think about just using the Boost Graph library?

It boils down to writing a short Traits class for your graph structure (and thus it is not necessary to alter your graph definition/header) and is - at least for these fundamental algorithms - proven to be working stable and correctly.

I'd always suggest not to reinvent the wheel especially when it comes to graphs and numerics...

Answer 3

The problem with Palo Alto -> Boston seems to be that the algorithm takes the route Palo Alto -> San Fransisco -> Los Angeles -> San Fransisco (edgesTaken = 3) and then fails the while condition because San Fransisco's been visited already.