CODEWITHSUNDEEP
c++algorithmgriddijkstrapath-finding
Muddy
Muddy

Reputation: 87

Dijkstra's algorithm returning incorrect values

I've hit a wall in attempting to understand Dijkstra's algorithm. The algorithm, in short, finds the shortest distances between A and B given distances between the two.

I will post my version of the algorithm (I haven't had much success looking online thus far), followed by the distances between nodes.

void GraphM::findShortestPath()
{
    for (int i = 1; i <= nodeCount; i++)    // From Node i...
    {
        for (int v = 1; v <= nodeCount; v++) // ...through Node v...
        {
            for (int w = 1; w <= nodeCount; w++) // ...to Node w
            {
                if (!T[i][w].visited || !T[i][v].visited)
                {
                    T[i][w].dist = min(T[i][w].dist, T[i][v].dist + C[v][w]);
                    T[i][v].visited = true;
                    T[i][w].visited = true;
                }           
            }
        }
    }

    cout << "1 to 2 is " << T[1][2].dist << endl; 
}

This outputs the following:

1 to 2 is 48

...when it should be

1 to 2 is 40

The values I'm working with are as follows:

1 2 50
1 3 20
1 5 30
2 4 10
3 2 20
3 4 40
5 2 20
5 4 25

...where, in each line, the first token is the first node, the second token is the second node, and the third token is the distance between those nodes (in the algorithm's case, these tokens would be i, v, and T[i][v].dist). In the algorithm, nodeCount is the number of nodes in the grid (5), and w is a node that we are looking for the distance to, from i. C[v][w] returns the original distance between v and w. So, if v was 5 and w was 2, C[v][w] would return 20. This is constant, whereas T[v][w].dist (for instance) can be changed.

Any nonexistant node relationships such as C[5][3] or T[1][4].dist (at least at the outset) return INT_MAX, which is equivalent to infinity.

Also, for anyone wondering; yes, this is a homework assignment. Unfortunately, my professor has necessitated some specific details (such as using a struct T), and she never went into much detail on how to write Dijkstra's algorithm into code, other than a somewhat vague outline. I am simply asking if someone can tell me what I am doing wrong and how to fix it, if possible.

Any help is very much appreciated and would save me a lot of time from banging my head against a wall.

Upvotes: 0

Views: 177

Answers (1)

David Mahone
David Mahone

Reputation: 237

This is not Dijkstra's algorithm. What you are trying to implement is Floyd-Warshall algorithm. This would find the minimum distance for all pair of vertices.

http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

Note that the first loop loops through the transfer node. With this implementation you don't need to remember which edge you already visited.

void GraphM::findShortestPath()
{  
    // Initialize T[i][j] to C[i][j] or MAX_INT here
    for (int k = 1; k <= nodeCount; k++)    // Through Node k...
    {
        for (int u = 1; u <= nodeCount; u++) // ...From Node u...
        {
            for (int v = 1; v <= nodeCount; u++) // ...to Node v
            {
                // if going through k provides a cheaper path, update T[u][v]
                T[u][v] = min(T[u][v], T[u][k] + T[k][v]);           
            }
        }
    }

    cout << "1 to 2 is " << T[1][2]<< endl; 
}

Upvotes: 1

Related Questions