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]
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 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.
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
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments