Dijkstra's Algorithm using Adjacency Matrix not finding correct distance/path from each node to every other node

Question

I'm trying to write a program that builds a graph using an Adjacency Matrix and then finds the shortest path from each node to every other node using Dijkstra's Algorithm. My program is current not capable of finding the correct shortest paths every time. I also need to track the path, but I am unsure where to even start.

class GraphD
{

public:
    GraphD();
    void buildGraph(ifstream &infile);

    void insertEdge(int from, int to, int distance);

    void findShortestPath();

private:
    static const int MAXNODES = 101;
    static const int infinity = 2147483647;
    struct TableType
    {
         bool visited;
         int dist;
         int path;
    };
    int C[MAXNODES][MAXNODES]; // holds adjacency matrix
    int size;
    TableType T[MAXNODES][MAXNODES]; // for dijkstra's algorithm
};


#include "GraphD.h"

GraphD::GraphD()
{
    size = 0;
    for(int i = 1; i < MAXNODES; i++)
    {
        for(int j = 1; j < MAXNODES; j++)
        {
            C[i][j] = infinity;
            T[i][j].dist = infinity;
            T[i][j].visited = false;
            T[i][j].path = 0;
        }
    }
}

void GraphD::buildGraph(ifstream &infile)
{
    string line;
    if(getline(infile, line))
    {
        size = atoi(line.c_str());
        for(int i = 1; i <= size; i++)
        {
            getline(infile, line);
            data[i] = line;
        }

        int vertex1, vertex2, distance;
        while(getline(infile, line))
        {
            stringstream edge(line);
            edge >> vertex1 >> vertex2 >> distance;
            if(vertex1 == 0)
                break;
            insertEdge(vertex1, vertex2, distance);
        }
        for(int i = 1; i <= size; i++)
        {
            C[i][i] = 0;
        }
    }
}

void GraphD::insertEdge(int from, int to, int distance)
{
    C[from][to] = distance;
} 

void GraphM::findShortestPath()
{
    for(int source = 1; source <= size; source++)
    {
        T[source][source].dist = 0;
        for(int i = 1; i <= size; i++)
        {
            int v = 0;
            int shortestDistance = infinity;
            for(int j = 1; j <= size; j++)
            {
                if((C[source][j] < shortestDistance) && !T[source][j].visited)
                {
                    shortestDistance = C[source][j];
                    v = j;
                }
            }
            T[source][v].visited = true;
            for(int w = 1; w <= size; w++)
            {
                if(!T[v][w].visited)
                {
                    T[v][w].dist = min(T[v][w].dist, T[source][v].dist + C[v][w]);
                }
            }
        }
    }
}

Have you even tried reading Wikipedia? findShortestPath() does not even begin to attempt to implement Dijkstra's algorithm. — Xarn
for(int i = 1; i <= size; i++) arrays are usually indexed [0,size) not [1,size] — Martin York

x1Mike7x x1Mike7x · Accepted Answer · 2015-11-12T09:07:59

Set infinity value equal to 1'000'000'000 (or smth like this), because when you use MAX_INT value you get integer overflow here

T[v][w].dist = min(T[v][w].dist, T[source][v].dist + C[v][w]);

Also, I think you should replace following part of code

if(!T[v][w].visited)
{
    T[v][w].dist = min(T[v][w].dist, T[source][v].dist + C[v][w]);
}

to the next one

if(!T[source][w].visited)
{
    T[source][w].dist = min(T[source][w].dist, T[source][v].dist + C[v][w]);
}

because you need to find distance to vertex W from vertex Source, not V.

Dijkstra's Algorithm using Adjacency Matrix not finding correct distance/path from each node to every other node

1 Answers