使用递归和逆序打印 Dijkstra SSSP

Question

我正尝试按特定顺序打印 SSSP，但卡住了。

假设我有 2 个数组：

节点 = [0, 1, 2, 3] 预测 = [-1, 2, 0, 1]

这是我想出的代码：

void printPath (int currentNode) {
    if (pred[currentNode] == -1) {
        printf("%d\n", currentNode);
        return;
    } else {
        printf("%d-", currentNode);
        return printPath (pred[currentNode]);
    }
}

printPath(1);

此代码 returns 节点 1 的路径为：1-2-0。当我想要的结果是0-2-1.

用我写的递归函数能达到这个结果吗？

非常感谢！

Answer 1

只需将printf节点语句移到递归调用后执行即可。

int node[] = {0, 1, 2, 3};
int pred[] = {-1, 2, 0, 1};
...
void printPath (int cnode) {
    if (-1 == pred[cnode]) {
        printf("\n%d", cnode);
        return;
    } else {
        printPath (pred[cnode]);
        printf("->%d", cnode);
    }
}
...
printPath(1);

使用递归和逆序打印 Dijkstra SSSP

Printing Dijkstra SSSP with recursion and in reverse order

c

recursion

dijkstra