Dijkstra算法。为什么需要寻找队列中的最小距离元素？

Question

我写了这个Dijksta算法的实现，在循环的每一次迭代中 while Q is not empty 而不是寻找队列的最小元素，而是取队列的头部。

以下是我写的代码

#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;
}

我对我找到的所有测试用例都运行了这个，它给出了一个正确的答案。我的问题是，为什么我们需要找到最小值呢？谁能给我解释一下？ 浅显易懂 ? 另外我需要一个测试用例来证明我的代码是错误的。

Answer 1

看一下这个例子。

1-(6)-> 2 -(7)->3
  \          /
   (7)     (2)
     \    /
       4

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

希望这能让你明白。

EDIT：对不起，这个例子没有刹住代码。看看这个吧。

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 这里是一个链接 意象派

Answer 2

我认为你的代码的时间复杂度是错误的，你的代码比较了（几乎）所有的节点，这是二次元的时间复杂度。你的代码比较了（几乎）所有的节点对，这是二次元的时间复杂度。

尝试添加10000个节点和10000条边，看看代码是否能在1秒内执行。

Answer 3

始终必须找出最小距离的未访问顶点，否则你将至少弄错一条边。例如，考虑以下情况

4 4 1 2 8 2 4 5 1 3 2 3 2 1

             (8)   (5)
           1-----2----4
            \   /  
          (2)\ / (1) 
              3

而我们从 vertex 1

distance[1]=0

当你访问 vertex 1 你已经放松了 vertex 2 和 vertex 3那么现在

distance[2]=8 和 distance[3]=2

在这之后，如果我们不选择最小值而选择了 vertex 2 反之，我们得到

distance[4]=13

然后选择 vertex 3 这将给

distance[2]=3

于是我们就有了 distance[4]=13 本应

distance[4]=8

因此，我们应该在Dijkstra的每个阶段从未访问的地方选择最小值，这可以有效地使用 priority_queue.