c - 在 Dijkstra 算法中获取实际路径

Question

我有一段代码使用 Dijkstra 算法来获取从一个顶点到另一个顶点的最短路径的成本。它读取一个文本文件，其中包含第一行的顶点数，文件的其余部分是成本邻接矩阵。我还需要获取顶点之间经过的实际路径，但我无法弄清楚那部分。我的代码如下。如您所见，我未能创建合适的前置数据结构:

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

FILE *fp;

typedef enum { false, true } bool; //creating a "bool" data type

void readFromFile(char *out){ //reading from file

    fgets(out, 1000, fp);

}

void loadFile(){ //loading file
    fp = fopen("graphmatrix.txt","r");
    if(fp==NULL){
        printf("graphmatrix.txt not found.\n");
        exit(1);
    }   
} 

void convertToInt (char *arr, int *matrix) { //parsing lines from text file into int array
    int num, i = 0, len;
    while (sscanf(arr, "%d%n", &num, &len) == 1) {
        matrix[i] = num;
        arr += len;
        i++;            
    }
}

void dijkstra(int src, int vertices, int graph[vertices][vertices]) { //dijkstra's algo
    int i;
    int count;
    int v;
    int dist[vertices]; //will hold the shortest distances (so far) from source to vertex
    int pred[vertices][vertices];
    int predCount = 0;

    bool sptSet[vertices]; //sptSet[i] will be true if vertex i is done processing (in class 1)

    //initialize all distances as infinity (int_max) and stpSet[] as false (in class 2)
    for (i = 0; i < vertices; i++){
        dist[i] = INT_MAX;
        sptSet[i] = false;
        pred[i][i] = INT_MAX;
    }

    dist[src] = 0; //distance from source to itself is 0

    for (count = 0; count < vertices - 1; count++) { //gets shortest distances
        printf("**COUNT = %d**\n", count + 1);
        int u = minDistance(dist, sptSet, vertices);
        printf("u = %d\n", u);
        sptSet[u] = true; //marks current vertex as done

        for (v = 0; v < vertices; v++) { //updates distances
            printf("in count %d, v = %d\n", count, v);
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){
                dist[v] = dist[u] + graph[u][v];
                printf("dist[%d] = %d\n", v, dist[v]);
                pred[count][predCount] = u;
                predCount++;
                }
        }
    }

    printSolution(dist, vertices, src, pred[src]);

}

int minDistance(int dist[], bool sptSet[], int vertices) { //checks if new distance is smaller than current distance
    int min = INT_MAX, min_index;
    int v;

    printf("\n---minDistance function---\n\n");

    for (v = 0; v < vertices; v++){
        printf("v = %d\n", v);
        if (sptSet[v] == false && dist[v] <= min){
            min = dist[v], min_index = v;
            printf("min: %d\n", min);
            printf("min_index: %d\n", min_index);
            }
    }
    printf("\n---exit minDistance---\n\n");
    return min_index;
}

int printSolution(int dist[], int vertices, int src, int pred[]) { //prints distance and path to screen
    int i, j;
    for (i = 0; i < vertices; i++){
        printf("vertex %d to vertex %d: %d\n", src + 1, i + 1, dist[i]);    
        printf("path: ");
        for (j = 0; j < vertices; j++){
            printf("%d -> ", pred[j]);
        }
    }
}

int main(){

    int i, j;
    int vertices;
    char tempvertices[10];
    char temp;

    loadFile();
    readFromFile(tempvertices);

    vertices = tempvertices[0] - '0';

    char matrixLines[vertices][100];
    int matrix[vertices][vertices];

    for (i = 0; i < vertices; i++){
        readFromFile(matrixLines[i]);
        convertToInt(matrixLines[i], matrix[i]); 
    }

    for (j = 0; j < vertices; j++){
        printf("\n-----------------DIJKSTRA number %d-------------------\n\n", j + 1);
        dijkstra(j, vertices, matrix);
    }

    return 0;
}

示例文本文件(名为 graphmatrix.txt):

3
0 3 1
1 0 4
1 2 0

请帮忙获取路径，好吗？

Answer 1

如果我没记错的话，您似乎想更新 pred[v] = u，其中 pred 只是一维的。在生成的最短路径树中，每个顶点都只有一个前驱，即在相应的最小操作中被选中的前驱。我想在 minDistance 中设置 pred 会更容易。