CODEWITHSUNDEEP
pythonbreadth-first-searchshortest-pathdijkstra
user2961927
user2961927

Reputation: 1718

What's wrong with BFS for finding shortest path lengths in weighted directed graph

Dijkstra's algorithm is the go-to method for finding the shortest path lengths between a source node and all the other nodes in a directed graph with nonnegative edge weights. I am wondering why the following plain BFS is not used more often?

distanceTo[sourceNode] = 0 # All the other entries are Inf.
frontier = [sourceNode]


# In Python, assume the graph is stored in a dictionary of dictionaries G. 
# G[x] retrives the neighors of node x, and G[x][y] gives weight of the edge
# from node x to node y.

while frontier:
  fnew = set() # New frontier.
  for x in frontier:
    neighbors = G[x]
    for y in neighbors:
      # Add y to the new frontier only if its distance to the
      # source node will change:
      if distanceTo[y] > distanceTo[x] + G[x][y]:
        distanceTo[y] = distanceTo[x] + G[x][y]
        fnew.add(y)
  frontier = fnew

Is the algorithm incorrect or does it have some flaws? Thanks!

Upvotes: 0

Views: 230

Answers (1)

kaya3
kaya3

Reputation: 51063

The issue is performance. With Dijkstra's algorithm, it is guaranteed that when you take and remove a node from the frontier, its shortest path has been found, and that node will never be re-inserted into the frontier. So the total number of iterations of the outer loop is at most the number of nodes in the graph.

On the other hand, if you don't prioritise nodes by distance (such as in BFS, where nodes are prioritised by "number of edges" which is not the same as distance in a weighted graph), then each time you take and remove a node from the frontier, a shorter path to that node might yet be found via some other node in the frontier which you will consider later. That means each node may have to be processed many times.

Upvotes: 2

Related Questions