c - 打印图中所有可能的最短路径

Question

我正在编写一些代码，使用 Dijkstra 算法的修改版本打印图形中所有可能的最短路径。在经典实现中，您有一个数组，其中存储每个节点的前身，而我创建了一个矩阵，其中每个节点可以有多个前身，这样您就可以沿着从一个节点到源的多条路径。问题是，我只是不知道如何打印它。我写了这段代码，但它没有提供正确的解决方案:

void print(graph grf, int node) {
    int n;
    if (grf->preds[node][0] == NIL) {
        printf("\n%i", node);
        return;
    }
    else {
        for (n = 0; n<grf->number; n++) {
            if (grf->preds[node][n] != NIL) {
                print(grf, grf->preds[node][n]);
                printf("->%i", node);
            }
        }
    }
    return;
}

它打印出以下解决方案:

1->0
1->9->8
1->3->7
1->0->7->8->2
1->3
1->9->4
1->3->5
1->0->5
1->3->7
1->0->7->6
1->9->8
1->3->7
1->0->7->8->6
1->3->7
1->0->7
1->9->8
1->3->7
1->0->7->8
1->9

虽然这是正确的(请注意顺序并不重要):

1->9
1->9->8
1->9->8->6
1->9->8->2
1->9->4
1->3
1->3->7
1->3->7->8
1->3->7->8->6
1->3->7->8->2
1->3->7->6
1->3->5
1->0
1->0->7
1->0->7->8
1->0->7->8->6
1->0->7->8->2
1->0->7->6
1->0->5

我认为这是因为当您有两个可能的前任并且您正在从另一个调用返回时 for 循环再次调用该函数，但我不知道如何避免这种情况并且仍然有一个简单且良好的工作代码。

我有一个建议是使用 BFS 或 DFS 来打印路径，但我不明白如何。

Answer 1

好的，如果有人感兴趣，我解决了这个问题。我创建了一个临时数组来存储路径，当函数到达终点时，它会打印所有数组。有一个在每次调用时递增的变量，它存储递归的深度并告诉函数数组的哪个位置存储节点。这是代码:

void stampa(p_grafo grf, int nodo, int depth) {
int contatore, i;
if (grf->preds[nodo][0] == NIL) {
    printf("%i", nodo);
    for(i=grf->numero-1;i>=0;i--)
        if(grf->temp[i]!=NIL)
            printf("->%i", grf->temp[i]);
    printf("\n");
    return;
}
else {
    for (contatore = 0; contatore<grf->numero; contatore++) {
        if (grf->preds[nodo][contatore] != NIL) {
            grf->temp[depth]=nodo;
            stampa(grf, grf->preds[nodo][contatore], depth+1);
        }
    }
}
return;
}