Dijkstra Algorithm

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

Here is my implementation:

#include 
#include 

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

void print(int V)
{
    int i ;

    for (i = 0; i  0)
    {
        u = extractMin(V);
        inSet[u] = 1;
        q[u] = 0;

        for (i = 0; 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 105, would my code be efficient enough? Or do I need any modifications?

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.

StackExchange Code Review Q#96980, answer score: 7