12

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

我为我找到的所有测试用例运行了这个，它给出了正确的答案。
我的问题是为什么我们需要找到最小值？谁能用简单的英语向我解释一下？我还需要一个测试用例来证明我的代码是错误的。

4

4 回答 4

3

看看这个样本：

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 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上的链接

于 2013-01-04T15:01:46.963 回答
2

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

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

于 2013-01-04T15:06:18.900 回答
2

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

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 的每个阶段从 unvisited 中选择最小值，这可以使用priority_queue.

于 2020-06-13T17:06:23.367 回答
0

如果您为下图运行算法，则取决于子项的顺序。假设我们正在寻找从 1 到 4 的最短路径。

反例

如果你从 1 开始的队列，

dist[1] = 0
dist[2] = 21
dist[3] = 0

并且seen = {1}当队列被推送时2，3现在如果我们从队列中消耗 2，它将生成dist[4] = 51, seen={1,2}, q = [1 ,2,3,4]并且下次3从队列中消耗的时间2不会再次添加到队列中，因为它已经在seen. 因此，该算法稍后会将距离更新为 12+31=43 ，1->3-5->4但最短路径是 32 并且它是 on 1->3->2->4。

让我用代码示例讨论一些其他方面。假设我们有一个连接列表，(u,v,w)其中 nodeu有一个加权和有向边到vweight w。让我们准备如下图和边：

graph, edges = {i: set() for i in range(1, N+1)}, dict()
for u,v,w in connection_list:
    graph[u].add(v)
    edges[(u,v)] = w

ALGORITHM1 - 如果未访问，则选择要添加的任何孩子

q = deque([start])
seen = set()
dist = {i:float('inf') for i in range(1, N+1)}
dist[start] = 0

while q:
    top = q.pop()
    seen.add(top)
    for v in graph[top]:
        dist[v] = min(dist[v], dist[top] + edges[(top, v)])
        if v not in seen:
            q.appendleft(v)

这个已经在上面讨论过了，它会给我们错误的结果 43 而不是 32 用于 1 和 4 之间的最短路径。

问题不在于将 2 重新添加到队列中，然后让我们seen再次摆脱和孩子。

ALGORITHM2 - 再次将所有孩子添加到队列中

while q:
    top = q.pop()
    seen.add(top)
    for v in graph[top]:
        dist[v] = min(dist[v], dist[top] + edges[(top, v)])
        q.appendleft(v)

这在这种情况下会起作用，但它只适用于这个例子。这个算法有两个问题，

  1. 我们再次添加相同的节点，因此对于更大的示例，复杂性将取决于边数E而不是节点数V，对于密集图，我们可以假设O(E) = O(N^2)。
  2. 如果我们在图中添加循环，它将永远运行，因为没有停止检查。所以这个算法不适合循环图。

所以这就是为什么我们必须花费额外的时间来选择最小的孩子，如果我们用线性搜索来做，我们最终会得到与上面相同的复杂性。但是如果我们使用优先级队列，我们​​可以将最小搜索减少到O(lgN)而不是O(N). 这是代码的线性搜索更新。

ALGORITHM3 - 具有线性最小搜索的 Dijkstra 算法

q = [K]
seen = set()
dist = {i:float('inf') for i in range(1, N+1)}
dist[start] = 0

while q:
    min_dist, top = min((dist[i], i) for i in q)
    q.remove(top)
    seen.add(top)
    for v in graph[top]:
        dist[v] = min(dist[v], dist[top] + edges[(top, v)])
        if v not in seen:
            q.append(v)

现在我们知道了下一次可以记住使用堆来获得最优 Dijkstra 算法的思考过程。

于 2020-07-10T22:26:02.983 回答