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!