gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:13:10 25 4
gpt4 key购买 nike

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

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

最佳答案

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

关于c++ - 修改 Dijkstra 算法以打印最短路径中的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5330463/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com