谁能说出我的算法为什么错误? [英] Can anyone tell why my algorithm is wrong?

问题描述

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

I was working on single source shortest path problem and I made a modification to bfs that can solve the problem. The algorithm runs in O(2E) times, I just can't understand why it is wrong (it must be otherwise dijstra's would not be most efficient algorithm).

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的算法中，优先级队列可确保在知道顶点与源的距离之前，不处理顶点.

In Dijkstra's algorithm, the priority queue ensures that you don't process a vertex until you know it's distance from the source.

BFS没有此属性.如果到顶点的最短路径比边缘最少的路径具有更多的边缘，那么将过早处理它.

BFS doesn't have this property. If the shortest path to a vertex has more than edges than the path with the fewest edges, then it will be processed too early.

例如，当您想要从 S 到 T 的最短路径时，请考虑以下图表:

Consider this graph, for example, when you want the shortest path from S to T:

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

顶点 C 将在顶点 B 之前被访问.您会认为到 C 的距离是5，因为您还没有发现更短的路径.当访问 C 时，它将为 T 分配6的距离.这是错误的，并且永远不会得到解决，因为 C 不会再次被访问.

Vertex C will be visited before vertex B. You will think the distance to C is 5, because you haven't discovered the shorter path. When C is visited, it will assign a distance of 6 to T. This is incorrect, and will never be fixed, because C will not be visited again.

这篇关于谁能说出我的算法为什么错误?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！