c++ - 修改 Dijkstra 算法以打印最短路径中的节点

Question

我想知道如何修改这个函数来保存节点的最终最短路径。这是我的课本，稍作修改。

template <class vType, int size>
void weightedGraphType<vType, size>::shortestPath(vType vertex) {
int i, j;
double minWeight;

for (j = 0; j < gSize; j++) {
    smallestWeight[j] = weights[vertex][j];
}

bool weightFound[size];

for (j = 0; j < gSize; j++) {
    weightFound[j] = false;
}

for (i = 0; i < gSize; i++) {
    int v;
    cout << vertex << " to " << i << endl;
    minWeight = INFINITY;

    for (j = 0; j < gSize; j++) {
        if (!weightFound[j]) {
            if (smallestWeight[j] < minWeight) {
                v = j;
                minWeight = smallestWeight[v];
            }
        }
    }

    weightFound[v] = true;

    for (j = 0; j < gSize; j++) {
        if (!weightFound[j]) {
            if (minWeight + weights[v][j] < smallestWeight[j]) {
                smallestWeight[j] = minWeight + weights[v][j];
            }
        }
    }
} //end for
} //end shortestPath

Answer 1

这里有一个提示:对于每个节点，您知道您找到的达到它的最小权重。您还可以在到达此节点之前知道“到达此节点的最短路径”来自何处。