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!