Unreachable Node in Dijkstra's Algorithm

Question

So I'm having trouble with Dijkstra's algorithm (src to dest). I looked at other answers and could not find the solution to my problem. I have used an adjacency list, thus I have a list for vertices, and each vertex has it's own edge list. My problem arises when I have a node that is unreachable. Specifically, it never gets visited thus I'm stuck in my allNotComp while loop. Can anyone help me with a solution? Code is below.

#include <stdlib.h>
#include <stdio.h>
int INFINITY = 9999;

struct edge
{
 int vertexIndex;
 int vertexWeight;
 struct edge *edgePtr;
} edge;

struct vertex
{
 int vertexKey;
 struct edge *edgePtr;
 struct vertex *vertexPtr;
}vertex;

struct vertex *Start = NULL;

void insertEdge(int vertex, int vertex2, int vertexWeight);

void insertVertex(int vertexKey);

int allNotComp(int comp[], int size);

void printPath(int prev[], int src, int dest, int size);

void dijkstra(int src, int size, int dest);

int cost(int curr, int i);

int main(int argc, char * argv[]) {

int k = 1;
int numVertices = atoi(argv[2]);
char* source = argv[3];
char* destination = argv[4];
int src = atoi(argv[3]);
int dest = atoi(argv[4]);
Start = &vertex;
Start->vertexKey = 0;
Start->vertexPtr = NULL;
Start->edgePtr = NULL;
int m = 0;
int flag = 0;
int flag2 = 0;

for(m = 0; m < numVertices; m++){
if(src == m) {
flag = 1;
}
if(dest == m) {
flag2 = 1;
}
}
if(!(flag && flag2)) {
printf("%s ", "ERROR: Src and/or Dest not valid.\n");
exit(0);
}

while(k < numVertices) {
insertVertex(k);
k++;
}

FILE *f = fopen(argv[1], "r");
int numbers[numVertices][numVertices];
char ch;
int i = 0;
int j = 0;

 for(m = 0; m < numVertices*numVertices; m++) {
 fscanf(f, "%d", &(numbers[i][j]));
 j=j+1;
if(j == numVertices) {
i=i+1;
j=0;
}
}



for(i=0;i<numVertices;i++) {
for(j=0;j<numVertices;j++) {
if(i == j && numbers[i][j] != 0) {
printf("%s", "ERROR: All diagonals must be zero.\n");
exit(0);
}
if(i != j) {
insertEdge(i, j, numbers[i][j]);
}
}
}

dijkstra(src, numVertices, dest);
}

void insertEdge(int vertex, int vertex2, int vertexWeight)
{
if(vertexWeight == -1) return;

struct vertex *traverse;
if(vertex == Start->vertexKey) {
traverse = Start;
}
else {
while(traverse->vertexKey != vertex) {
traverse = traverse->vertexPtr;
}
}
struct edge *e,*e1,*e2;
e=traverse->edgePtr;
while(e&& e->edgePtr)
{
    e=e->edgePtr;
   }
   e1=(struct edge *)malloc(sizeof(*e1));
   e1->vertexIndex=vertex2;
  e1->vertexWeight = vertexWeight;
    e1->edgePtr=NULL;
    if(e)
    e->edgePtr=e1;
    else
     traverse->edgePtr=e1;
}

void insertVertex(int vertexKey) {
struct vertex *v, *v1, *v2;
v = Start->vertexPtr;
while(v && v->vertexPtr) {
v=v->vertexPtr;
}
v1=(struct vertex *)malloc(sizeof(*v1));
v1->vertexKey = vertexKey;
v1->vertexPtr = NULL;
v1->edgePtr = NULL;
if(v) {
v->vertexPtr = v1;
}
else {
Start->vertexPtr = v1;
}
}

void dijkstra(int src, int size, int dest) {

int comp[size];
int dist[size];
int prev[size];
int i;
for(i = 0; i<size; i++) {
    comp[i] = 0;
    dist[i] = INFINITY;
    prev[i] = -1;
    }
comp[src] = 1;
dist[src] = 0;
prev[src] = src;
int curr = src;
int k;
int minDist;
int newDist;
while(allNotComp(comp, size)) {
    minDist = INFINITY;
    for(i = 0; i<size;i++) {
        if(comp[i] == 0) {
            newDist = dist[curr] + cost(curr, i);
            if(newDist < dist[i]) {
                    dist[i] = newDist;
                    prev[i] = curr; }
                if(dist[i] < minDist) {
                    minDist = dist[i];
                    k=i; }
            }
        }
curr = k;
comp[curr] = 1;

    }
    if(dist[dest] < INFINITY) {
         printPath(prev, src, dest, size);
         printf(":%d\n", dist[dest]);
    } else {
        printf("%s\n", "NO PATH EXISTS BETWEEN THE TWO VERTICES!");
    }
}

int allNotComp(int comp[], int size) {
    int i;
    for(i = 0; i < size; i++) {
        if(comp[i] == 0) {
            return 1;
        }
    }
    return 0;
}

int cost(int curr, int i) {
    struct vertex *travel;
    struct edge *traverse;

    travel = Start;
    while(travel->vertexPtr != NULL) {
        if(travel->vertexKey != curr) {
            travel = travel->vertexPtr;
        }
        else{
            break;
        }
    }

    traverse = travel->edgePtr;
    while(traverse->edgePtr != NULL) {
        if(traverse->vertexIndex != i) {
            traverse = traverse->edgePtr;
        }
        else{
            break;
        }
    }
    if(traverse->vertexIndex != i) {
        return INFINITY; 
    }

    return traverse->vertexWeight;
}

void printPath(int prev[], int src, int dest, int size) {
if(src == dest) {
printf("%d", src);
}

else {
printPath(prev, src, prev[dest], size);
printf("-%d", dest);
}

}

Answer 1

Although an unreachable node never gets visited, this situation can be detected. If the dists of all unvisited nodes are INFINITY, this means all remaining nodes are unreachable, and you should end the loop.