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

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]

标签： algorithmshortest-path

Answer 1

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

BFS 没有这个属性。如果到顶点的最短路径的边数多于边数最少的路径，则处理得太早。

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

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

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