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 how slower the following algorithm is than Dijkstra's? What about its average and worst-case time complexities?

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]
  frontier = fnew

Could someone help and show some reference to the answer? Thanks!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy