c - 如何通过C语言中的Dijkstra算法在无向图中查找和保存并行最短路径

Question

我有以下图表：

A-B,11
A-C,10
B-D,5
C-D,6
C-E,15
D-E,4

任务是找到最短路径、打印路径和到所有对的距离，如下所示：

Path: A -> D
Route: A -> C -> D
Distance: 10 + 6 = 16

在该图示例中，我们几乎没有重复的路径，但有不同的路径，如下所示：

Route: A -> B -> D
Route: A -> C -> D

我需要保存所有这些不同的路径并在最后打印。现在程序查找并打印除这些情况之外的所有路径。我尝试了很多选择，但由于某种原因，我无法理解如何解决这个问题。我将权重存储在二维数组中，如下所示：

    A    B    C    D    E
A   0   11   10    0    0
B  11    0    0    5    0
C  10    0    0    6   15
D   0    5    6    0    4
E   0    0   15    4    0

我的代码如下：

...
typedef struct s_way_dijkstra {
    int isld_nm;
    bool is_chk;
    int parent;
    struct s_way_dijkstra *next;
}t_way_dijkstra;

void printDistance(t_way_dijkstra *djk_var, int j) {
    if (djk_var[j].parent == -1 )
        return;

    printDistance(djk_var, djk_var[j].parent);   
    if (djk_var[j].parent != 0 ) 
    printstr("+ ");
    printint(djk_var[j].isld_nm - djk_var[djk_var[j].parent].isld_nm); 
    printstr(" ");

    // for (;i > 0 && djk_var->parent[i] != -1; i--)
        // printf("%d ", j);
}

void printRoute(t_way_dijkstra *djk_var, int j, char **isld) {
    if (djk_var[j].parent == -1)
        return;

    printRoute(djk_var, djk_var[j].parent, isld); 
    printstr(" -> ");
    printstr(isld[j]); 
}

static void printSolution(t_way_dijkstra *djk_var, int n, char **isld, int src) {

    for (int i = 0; i < n; i++)
        printf("%d ", djk_var[i].isld_nm);
    printf("\n");

    printf("\nparent\n");
    for (int i = 0; i < n; i++)
        printf("%d ", djk_var[i].parent);
    printf("\n");

    for (int i = src; i < n; i++) {
        if (djk_var[i].isld_nm != 0) {
            // Path
            printstr("Path: ");
            printstr(isld[src]);
            printstr(" -> ");
            printstr(isld[i]);

            // Route
            printstr("\nRoute: ");
            printstr(isld[src]);
            printRoute(djk_var, i, isld);
            printstr("\n");

            // Distance
            if (djk_var[i].parent >= 1) {
            printstr("Distance: ");
            printDistance(djk_var, i);
            printstr("= ");
            printint(djk_var[i].isld_nm);
            printstr("\n");
            }
            else {
                printstr("Distance: ");
                printint(djk_var[i].isld_nm);
                printstr("\n");
            }
        }
    }
}

static int get_min_distance(t_way_dijkstra *djk_var , t_main *vars) {
    int min_val = INT_MAX;
    int min_ind = 0;

    for (int i = 0; i < vars->nmb_isld; i++) {
        if (djk_var[i].is_chk == false && djk_var[i].isld_nm <= min_val) {
            min_val = djk_var[i].isld_nm;
            min_ind = i;
        }       
    }
    return min_ind;
}

static void dijkstra(int src, t_main *vars, t_graph *graph, t_way_dijkstra *djk_var) {
    int min_ind = 0;

    for (int i = 0; i < vars->nmb_isld; i++) {
        djk_var[i].parent = -1;
        djk_var[i].isld_nm = INT_MAX;
        djk_var[i].is_chk = false;
    }
    djk_var[src].isld_nm = 0;
    for (int i = 0; i < vars->nmb_isld; i++) {
        min_ind = get_min_distance(djk_var, vars);
        djk_var[min_ind].is_chk = true;
        for (int j = src; j < vars->nmb_isld; j++) {
            if (!djk_var[j].is_chk && graph->array[min_ind][j] 
            && djk_var[min_ind].isld_nm != INT_MAX
            && djk_var[min_ind].isld_nm + graph->array[min_ind][j] < djk_var[j].isld_nm) {  
                djk_var[j].parent = min_ind;
                djk_var[j].isld_nm = djk_var[min_ind].isld_nm + graph->array[min_ind][j];

            }
        }

    }

    printSolution(djk_var, vars->nmb_isld, graph->isld, src);
}
...

标签： calgorithmgraphpath