我编写了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; }
我为我发现的所有测试用例运行了这个,它给出了正确的答案.
我的问题是为什么我们需要找到最小值?任何人都可以用简单的英语向我解释这个吗?此外,我需要一个测试用例,证明我的代码错了.