0
$\begingroup$

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]
        fnew.add(y)
  frontier = fnew

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

$\endgroup$

0

Your Answer

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