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

我正在研究单源最短路径问题，我对 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]

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

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

例如，当您想要从S to T:

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

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