Dijkstra Algorithm

Question

I have implemented Dijkstra's Algorithm in C, using arrays instead of any structs.

Here is my implementation:

#include <stdio.h>
#include <stdlib.h>

int G[20][20], distance[20], inSet[20], q[20], parent[20];

void print(int V)
{
    int i ;

    for (i = 0; i < V; i++)
    {
        printf("i = %d parent = %d distance from source = %d\n", 
               i + 1, 
               parent[i], 
               distance[i]) ;
    }
}

int Q(int V)
{
    int sum = 0, i;

    for (i = 0; i < V; i++)
    {
        sum += q[i] ;
    }

    return sum ;
}

int extractMin(int V)
{
    int i, idx, min = 1000;

    for (i = 0; i < V; i++)
    {
        if (distance[i] <= min && inSet[i] == 0)
        {
            min = distance[i], idx = i;
        }
    }

    q[idx] = 0 ;
    return idx ;
}

void dijkstra(int S, int V)
{
    int u, i, check_empty = Q(V);

    while (check_empty > 0)
    {
        u = extractMin(V);
        inSet[u] = 1;
        q[u] = 0;

        for (i = 0; i < V; i++)
        {
            if (G[u][i] > 0)
            {
                if (distance[u] + G[u][i] < distance[i])
                {
                    distance[i] = distance[u] + G[u][i], parent[i] = u + 1;
                }
            }
        }

        check_empty = Q(V);
    }

    print(V);
}

int main()
{
    int V, i, j, S;
    printf("Enter no. of vertices: ");
    scanf("%d", &V);

    printf("Enter graph in matrix form:\n");

    for (i = 0; i < V; i++)
    {
        for (j = 0; j < V; j++)
        {
            scanf("%d", &G[i][j]);
        }
    }

    for (i = 0; i < V; i++)
    {
        distance[i] = 1000, inSet[i] = 0, q[i] = 1, parent[i] = -1;
    }

    printf("Enter the source vertex: ");
    scanf("%d", &S);
    distance[S - 1] = 0 ;
    dijkstra(S, V);
    return 0;
}

It's just a simple code, and I have given a bound size of 20 for now, just for simplicity.

My concerns:

• Is my code efficient enough? Or is there another more simple way to implement Dijkstra?

• Is it ok to use arrays instead of structs for graph implementation? Does it have any performance issues? I have seen a lot of codes on the internet which use structs such as struct Graph, or struct edge.

• Is using global variables better than local variables in my implementation? The variables I declared global in my code are the ones which are used in 2 or more functions, and I would have to send them as parameters if not global.

• If I make the code more adaptive by increasing the array sizes to, say 10⁵, would my code be efficient enough? Or do I need any modifications?

Answer 1

First: indentation and naming, indent the body of your functions so the separation between them is easier to see at a glance (they are indented on your blog so I'll assume it's a copy-paste fail). Descriptive names will make the code also much easier to follow (it took me some time to figure out what the q array was meant to be).

Besides that there are 2 design decisions I see slowing you down; one is not using a heap and the other is using a (non-sparse) adjacency matrix.

Both of these will slow down what Dijkstra could be.

The cost of the adjacency matrix is that you need to loop over all nodes even if there is only a few edges.

The cost of not using a heap to hold the unseen nodes is that finding the next node to consider is a \$O(n)\$ operation instead of a potential \$O(\log n)\$ operation.

Also why the aversion for structs a

struct Node{
    int nbNeighbours; 
    Node** neighbours; //see much smaller array to loop through to get the neighbors
    int* edgeCost; 
    int distance, seen, inSet;
    Node* parent;
}

is much easier to use.

Answer 2

Comma operator?

I don't like how you use of the comma operator to put multiple statements on one line. It makes it harder to see where each statement starts and ends. For example:

            if (distance[u] + G[u][i] < distance[i])
            {
                distance[i] = distance[u] + G[u][i], parent[i] = u + 1;
            }

At first glance it looks like you are simply assigning something to distance[i]. But if you expand it:

            if (distance[u] + G[u][i] < distance[i])
            {
                distance[i] = distance[u] + G[u][i];
                parent[i] = u + 1;
            }

you could more easily see that both distance[i] and parent[i] were being modified.

Also, if you really wanted to only use one line, you could use a semicolon instead of a comma. Although I see that in the original code listing there were no curly braces for the if statement so you needed to use the comma operator to keep everything in one statement.

Efficiency

If this is just a small demonstration problem with a limit of 20 vertices, there's no problem with using arrays and a matrix. The code is definitely much simpler than if you used lists or a heap.

For a larger problem set, many graphs are described by a small list of edges instead of a matrix. So for example, with your program, if you increased the graph size to 1000 vertices, you would need to input 1000000 matrix elements, even if the graph only had 2000 edges. That's why many graph algorithms use an adjacency list representation instead of a matrix representation.

As far as global variables, they are a sign of a "toy program". A real program would keep the graph and algorithm state in some kind of local structure, to be passed around to the helper functions. Otherwise, you could only ever have one graph in your entire program.