我编写了 Dijksta 算法的这个实现,它在循环的每次迭代中 当 Q 不为空时
不是寻找队列的最小元素,而是获取队列的头部。
这是我写的代码
#include <stdio.h>
#include <limits.h>
#define INF INT_MAX
int N;
int Dist[500];
int Q[500];
int Visited[500];
int Graph[500][500];
void Dijkstra(int b){
int H = 0;
int T = -1;
int j,k;
Dist[b] = 0;
Q[T+1] = b;
T = T+1;
while(T>=H){
j = Q[H];
Visited[j] = 1;
for (k = 0;k < N; k++){
if(!Visited[k] && Dist[k] > Graph[j][k] + Dist[j] && Graph[j][k] != -1){
Dist[k] = Dist[j]+Graph[j][k];
Q[T+1] = k;
T = T+1;
}
}
H = H+1;
}
}
int main(){
int src,target,m;
int a,w,b,i,j;
scanf("%d%d%d%d",&N,&m,&src,&target);
for(i = 0;i < N;i ++){
for(j = 0;j < N;j++){
Graph[i][j] = -1;
}
}
for(i = 0; i< N; i++){
Dist[i] = INF;
Visited[i] = 0;
}
for(i = 0;i < m; i++){
scanf("%d%d%d",&a,&b,&w);
a--;
b--;
Graph[a][b] = w;
Graph[b][a] = w;
}
Dijkstra(src-1);
if(Dist[target-1] == INF){
printf("NO");
}else {
printf("YES\n%d",Dist[target-1]);
}
return 0;
}
我对我找到的所有测试用例都运行了这个,它给出了正确的答案。
我的问题是为什么我们需要找到最小值?谁能用简单的英语给我解释一下?我还需要一个测试用例来证明我的代码是错误的。
最佳答案
看看这个示例:
1-(6)-> 2 -(7)->3
\ /
(7) (2)
\ /
4
即你有从1到2的长度为6的边,从2到3的长度为7的边,从1到4的长度为7的边和从4到3的边。我相信你的算法会认为从1到3的最短路径的长度为13到 2,而实际上最好的解决方案是长度为 9 到 4。
希望这能说明问题。
编辑:抱歉这个例子没有破坏代码。看看这个:
8 9 1 3
1 5 6
5 3 2
1 2 7
2 3 2
1 4 7
4 3 1
1 7 3
7 8 2
8 3 2
您的输出是Yes 8
。虽然路径 1->7->8->3
只需要 7 个。这是 ideone 上的链接
关于c - Dijkstra 算法 : Why is it needed to find minimum-distance element in the queue,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14159424/