谁能告诉我为什么我的算法是错误的？

Question

我正在研究单源最短路径问题，我对 bfs 进行了修改可以解决该问题。该算法运行时间为 O(2E) 次，我只是不明白为什么它是错误的（这一定是错误的，否则 dijstra 的算法将不是最有效的算法）。

def bfs_modified(G,src,des):
    intialize d(src)=0, and d(!src) = inf
    visited[all_vertex]=False
    q=queue(src)

    while q is not empty: 
        u=q.pop()
        if(not visited[u]):
            visited[u]=True
            for all v connected to u:
                  q.insert(v)
                  if(d[v]>d[u]+adj[u][v]):
                      d[v]=d[u]+adj[u][v]
    return d[des]

Answer 1

在 Dijkstra 算法中，优先级队列确保您在知道顶点与源的距离之前不处理该顶点。

BFS 没有这个属性。如果到顶点的最短路径的边数多于边数最少的路径，那么它将过早处理。

考虑此图，例如，当您想要从 S 到 T 的最短路径时：

S--5--C--1--T
|     |
1     1
|     |
A--1--B

顶点 C 将在顶点 B 之前被访问。你会认为到C的距离是5，因为你还没有发现更短的路径。当C被访问时，它会给T分配一个6的距离。这是不正确的，永远不会修复，因为 C 将不会再次访问。

谁能告诉我为什么我的算法是错误的？

Can anyone tell why my algorithm is wrong?

algorithm

shortest-path