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

我编写了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;
}

我为我发现的所有测试用例运行了这个,它给出了正确的答案.@H_403_7@我的问题是为什么我们需要找到最小值？任何人都可以用简单的英语向我解释这个吗？此外,我需要一个测试用例,证明我的代码错了.

解决方法

看一下这个样本：

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.虽然路径1-> 7-> 8-> 3仅取7.这是@L_403_0@上的链接

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

解决方法

猜你在找的C&C++相关文章