When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we have found the shortest path to it.
However, Dijkstra has no such guarantee, because the neighbours of each node are checked in no specific order. Therefore, we need a relaxation step to update the shortest path of each node if we later find a shorter path.
Instead of choosing a random neighbour, why not always follow the neighbour with the shortest path? I think that would guarantee we have always found the shortest path and no relaxation step is required. I implemented this in Python and it seems to work. Am I missing something?
from heapq import heappop, heappush def shortest_path_lengths(graph, source): dist = {} q = [(0, source)] while q: cur_dist, v1 = heappop(q) if v1 in dist: continue dist[v1] = cur_dist for v2, v1_to_v2_dist in graph[v1].items(): if v2 not in dist: # check it hasn't been visited already heappush(q, (cur_dist + v1_to_v2_dist, v2)) return dist graph = { 'a': {'b': 3, 'c': 5}, 'b': {'c': 1}, 'c': {'d': 4}, 'd': {}, } print(shortest_path_lengths(graph, 'a'))
