Dijkstra的算法：为什么需要在队列中找到最小距离元素

概述我编写了Dijksta算法的这个实现,它在循环的每次迭代中,而Q不是空的,而不是找到队列的头部队列的最小元素. 这是我写的代码 #include <stdio.h>#include <limits.h>#define INF INT_MAXint N;int Dist[500];int Q[500];int Visited[500];int Graph[500][500];vo 我编写了Dijksta算法的这个实现,它在循环的每次迭代中,而Q不是空的,而不是找到队列的头部队列的最小元素.

这是我写的代码

#include <stdio.h>#include <limits.h>#define INF INT_MAXint 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

即边缘长度为6从1到2,边缘长度7从2到3,边缘长度7从1到4,边缘从4到3.我相信你的算法会认为从1到3的最短路径长度为13通过2,而实际上最好的解决方案是长度9到4.

希望这说清楚.

编辑：对不起这个例子没有制动代码.看看这个：

8 9 1 31 5 65 3 21 2 72 3 21 4 74 3 11 7 37 8 28 3 2

您的输出为是8.虽然路径1-> 7-> 8-> 3仅取7.这是ideone上的链接

总结

以上是内存溢出为你收集整理的Dijkstra的算法：为什么需要在队列中找到最小距离元素全部内容，希望文章能够帮你解决Dijkstra的算法：为什么需要在队列中找到最小距离元素所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。