Dijkstra 算法中的不可达节点

Question

所以我在使用 Dijkstra 算法（从源到目标）时遇到了问题。我查看了其他答案，但找不到解决我问题的方法。我使用了邻接表，因此我有一个顶点列表，每个顶点都有自己的边列表。当我有一个无法访问的节点时，我的问题就出现了。具体来说，它永远不会被访问，因此我陷入了我的 allNotComp while 循环。谁能帮我解决问题？代码如下。

#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

虽然无法访问的节点永远不会被访问，但这种情况是可以检测到的。如果所有未访问的节点的dist都是INFINITY，这意味着所有剩余的节点都不可达，你应该结束循环。

Dijkstra 算法中的不可达节点

Unreachable Node in Dijkstra's Algorithm

c

dijkstra