的Dijkstra最短路徑算法無限循環

Question

以下是我的程序的完整代碼。 dijkstra函數有問題，而當我使用大於18的頂點id時，它停留在無限循環中。我嘗試不同的組合，並沒有看到任何問題，迄今爲止除了使用數量大於18我已經添加樣本「city_list.txt」和「weighted_list.txt」太多，如果你想自己編譯。

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

#define CITYLIST "city_list.txt" 
#define WEIGHTLIST "weight_list.txt" 
#define INFINITE 32700 
#define MAXV 100 

void editfile(FILE *fp); 
const char *readLine(FILE *fp); 
int citycode(char *string, char **cities, int vertices); 
int dijkstra(int weight[MAXV][MAXV], int source, int destination, char **cities, int v); 


int menu() { 
    printf("1. Shortest distance between point A and point B\n"); 
    printf("2. Shortest distance to all points from point A\n"); 
    printf("3. List of city codes\n"); 
    printf("0. Exit\n"); 
    int choice; 
    scanf("%d", &choice); 
    return choice; 
} 

int main() { 
    FILE *fp; 
    fp = fopen(CITYLIST, "r+"); 
    editfile(fp); 

    char *cities[MAXV]; // To store name of the cities 

    char buffer[100]; 
    memset(buffer, '\0', sizeof(buffer)); 
    int intbuffer; 

    int vertices = 0; // Number of vertices 
    readLine(fp); // Pass the first line 

    /** Read city names from city_list.txt and save them into 
     *cities[100] array. Find the number of vertices  */ 
    while(1) { 
     if(fscanf(fp, "%s %d", buffer, &intbuffer) < 0) 
      break; 
     int i = 0; 
     for(i = 0; buffer[i] != '\0'; i++) { 
      // Count inside buffer 
     } 
     cities[vertices] = (char *)malloc(i+1); 
     memset(cities[vertices], '\0', sizeof(*cities[vertices])); 
     strcpy(cities[vertices], buffer); 
     vertices++; 
    } 

    fclose(fp); 
    fp = fopen(WEIGHTLIST, "r+"); 
    editfile(fp); 
    readLine(fp); // Pass the first line 

    int weight[MAXV][MAXV], i, j; 
    for(i = 0; i < MAXV; i++) 
     for(j = 0; j < MAXV; j++) 
      weight[i][j] = INFINITE; 
    char buffer2[100]; 

    for(i = 0; i < vertices; i++) { 
     memset(buffer, '\0', sizeof(buffer)); 
     memset(buffer2, '\0', sizeof(buffer2)); 
     fscanf(fp, "%s %s %d", buffer, buffer2, &intbuffer); 
     int c1, c2; 
     c1 = citycode(buffer, cities, vertices); 
     c2 = citycode(buffer2, cities, vertices); 
     if(c1 == -1 || c2 == -1) 
      return -1; 
     weight[c1][c2] = intbuffer; 
     weight[c2][c1] = intbuffer; 
    } 

    int choice = menu(); 
    while(choice != 0) { 
     if(choice == 1) { 
      choice = -1; 
      int p1, p2; 
      printf("Point A: "); 
      scanf("%d", &p1); 
      printf("Point B: "); 
      scanf("%d", &p2); 
      printf("\n***************\n"); 
      dijkstra(weight, p1, p2, cities, vertices); 
      printf("***************\n\n"); 
     } else if (choice == 2) { 
      choice = -1; 
      int p1; 
      printf("Point A: "); 
      scanf("%d", &p1); 
      int i; 
      printf("\n***************\n"); 
      for(i = 0; i < vertices; i++) 
       if(p1 != i) 
        dijkstra(weight, p1, i, cities, vertices); 
      printf("***************\n\n"); 
     } else if (choice == 3) { 
      choice = -1; 
      int i; 
      printf("\n***************\n"); 
      for(i = 0; i < vertices; i++) 
       printf("%d. %s\n", i, cities[i]); 
      printf("***************\n\n"); 
     } 
     choice = menu(); 
    } 
    return 0; 
} 

void editfile(FILE *fp) { 
    while(1) { 
     char ch = fgetc(fp); 
     if(ch == '-') { 
      fseek(fp, ftell(fp)-1, SEEK_SET); 
      fputc(' ', fp); 
      fseek(fp, ftell(fp)-1, SEEK_SET); 
     } 

     if(ch == EOF) 
      break; 
    } 
    fseek(fp, 0, SEEK_SET); 
} 

const char *readLine(FILE *fp) { 
    int maxlinelength = 32; 
    char *line = (char *)malloc(sizeof(char) * maxlinelength); 
    char ch = getc(fp); 
    int counter = 0; 

    while(ch != '\n' && ch != EOF) { 
     if(counter == maxlinelength) { 
      maxlinelength += 32; 
      line = realloc(line, maxlinelength); 
     } 

     line[counter] = ch; 
     counter++; 
     ch = getc(fp); 
    } 

    line[counter] = '\0'; // Add null terminator 
    realloc(line, counter + 1); // Get rid of extra space 
    return line; 
} 

int citycode(char *string, char **cities, int vertices) { 
    int i; 
    for(i = 0; i < vertices; i++) { 
     if(strcmp(string, cities[i]) == 0) 
      return i; 
    } 
    return -1; 
} 

int dijkstra(int weight[MAXV][MAXV], int source, int destination, char **cities, int v) { 

    int distance[MAXV], previous[MAXV], dist, i, minid, min, path[100], p; 
    int selected[MAXV] = {0}; 

    for(i = 0; i < v; i++) { 
     distance[i] = INFINITE; 
     previous[i] = -1; 
    } 
    selected[source] = 1; // Source is selected 
    distance[source] = 0; // Source to source distance zero 

    while(selected[destination] == 0) { 
     min = INFINITE; 
     minid = 0; 

     for(i = 0; i < v; i++) { 
      dist = distance[source] + weight[source][i]; 
      printf("weight[%d][%d]: %d\n", source, i, weight[source][i]); 
      if(dist < distance[i] && selected[i] == 0) { 
       distance[i] = dist; 
       previous[i] = source; 
      } else if (min > distance[i] && selected[i] == 0) { 
       min = distance[i]; 
       if(i == 0) 
        minid = source; 
       else 
        minid = i; 
      } 
     } 
     source = minid; 
     selected[source] = 1; 
    } 
    source = destination; 
    p = 0; 
    while(source != -1) { 
     path[p] = source; 
     source = previous[source]; 
     p++; 
    } 
    printf("\n---\n"); 
    for(i = p-1; i > -1; i--) { 
     if(i == 0) 
      printf("%s", cities[path[i]]); 
     else 
      printf("%s -> ", cities[path[i]]); 
    } 
    printf("\nShortest distance: %d\n---\n\n", distance[destination]); 
    return distance[destination]; 
} 

city_list.txt

City-Code 
AAA-1 
BBB-2 
CCC-3 
DDD-4 
EEE-5 
FFF-6 
GGG-7 
HHH-8 
III-9 
JJJ-10 
KKK-11 
LLL-12 
MMM-13 
NNN-14 
OOO-15 
PPP-16 
RRR-17 
SSS-18 
TTT-19 
UUU-20 
WWW-21 
XXX-22 
ZZZ-23 

weight_list.txt時，有沒有途徑

City1-City2-Distance 
AAA-BBB-124 
AAA-CCC-123 
AAA-DDD-432 
AAA-EEE-653 
AAA-FFF-12 
BBB-CCC-54 
BBB-WWW-325 
BBB-XXX-146 
CCC-PPP-95 
CCC-RRR-69 
CCC-SSS-124 
DDD-JJJ-642 
DDD-SSS-5 
DDD-XXX-18 
DDD-RRR-301 
DDD-HHH-13 
EEE-KKK-567 
EEE-LLL-120 
EEE-MMM-400 
EEE-NNN-123 
EEE-OOO-542 
EEE-PPP-51 
XXX-SSS-49 
XXX-WWW-39 

Answer 1

你的算法實現卡住。算法的主循環沒有退出條件。

如果您有編號正確的城市，你會看到，還有，可能是 - 作爲你的城市的名單現在，數字有不符合程序實際使用的數字！請注意，在您的路線列表中沒有任何優勢進入GGG或ZZZ。

人去修補你的算法的方式將是對這一明確的條款添加到您的循環。例如：

// no vertex actually can have index v, so we can use it as a deadlock condition 
while(selected[destination] == 0 && source != v) { 
    min = INFINITE; 
    minid = v; 

    printf("minid = %d\n", minid); 
    for(i = 0; i < v; i++) { 
     dist = distance[source] + weight[source][i]; 
     printf("weight[%d][%d]: %d\n", source, i, weight[source][i]); 
     if(dist < distance[i] && selected[i] == 0) { 
      distance[i] = dist; 
      previous[i] = source; 
     } 
     if (min > distance[i] && selected[i] == 0) { 
      min = distance[i]; 
      minid = i; 
     } 
    } 
    selected[source] = 1; 
    source = minid; 
    getc(stdin); 
} 
if(selected[destination] == 0 && source == v) 
{ 
    printf("\nThere is no route!\n"); 
    return distance[destination]; // will be INFINITE 
}