Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?

Dijkstra's algorithm

• Like BFS for weighted graphs.
• If all costs are equal, Dijkstra = BFS

Source : https://cs.stanford.edu/people/abisee/gs.pdf

From implementation perspective, the Dijkstra's algorithm could be implemented exactly like a BFS by swapping the queue with a priority queue.

Source

There is a confusion about this, it is possible to use modified BFS algorithm to find a shortest path in a weighted directed graph:

1. Use priority queue instead of a normal queue
2. Don't track visited nodes, and instead track distance from the starting node

Because of 2, some nodes will be visited more then once, which makes it less efficient comparing to Dijkstra.

shortest = sys.maxsize

queue = [(0, src, 0)]
while queue:
    (cost, node, hops) = heapq.heappop(queue)
    if node == dst:
        shortest = min(distance, cheapest)
    for (node_to, node_distance) in edges[node]:
        heapq.heappush(queue, (cost + node_distance, node_to, hops + 1))

• BFS only works when you’re counting shortest path as number of steps edges, or whatever application assigns identical (but positive) weights to all edges.
• The difference between BFS and Dijkstra is just replacing the FIFO queue with a priority queue!

Note that this doesn’t fix the positive weights constraint on edges, a famous shortcoming Dijkstra (and BFS) has that is fixed by Bellman-Ford by paying a speed penalty

Source: Chapters 8.4, 8.6 in Erickson, Jeff (2019). Algorithms

Both BFS and Dijkstra could be used to find the shortest path. The difference in how the shortest path is defined:

• BFS: path with the smallest number of edges (assuming the same weight for every edge or no weight).
• Dijkstra: path with the smallest weight along the path.

Consider this undirected connected graph:

We want to find the shortest path from A to F:

• BFS: A->C->E->F
• Dijkstra: A->C->E->D->F

Implementation is quite similar, the crucial part of Dijkstra is priority queue usage. I used Python for demonstration:

graph = {
    'A': {('B', 2), ('C', 1)},
    'B': {('A', 2), ('C', 4), ('D', 3)},
    'C': {('A', 1), ('B', 4), ('E', 2)},
    'E': {('C', 2), ('D', 1), ('F', 4)},
    'D': {('B', 3), ('E', 1), ('F', 2)},
    'F': {('D', 2), ('E', 4)}

}


def dijkstra(graph, start: str):
    result_map = defaultdict(lambda: float('inf'))
    result_map[start] = 0

    visited = set()

    queue = [(0, start)]

    while queue:
        weight, v = heapq.heappop(queue)
        visited.add(v)

        for u, w in graph[v]:
            if u not in visited:
                result_map[u] = min(w + weight, result_map[u])
                heapq.heappush(queue, [w + weight, u])

    return dict(result_map)

print(dijkstra(graph, 'A'))

Output:

{'A': 0, 'C': 1, 'B': 2, 'E': 3, 'D': 4, 'F': 6}

While for BFS ordinary queue is sufficient:

graph = {
    'A': {'B', 'C'},
    'B': {'A', 'C', 'D'},
    'C': {'A', 'B', 'E'},
    'E': {'C', 'D', 'F'},
    'D': {'B', 'E', 'F'},
    'F': {'D', 'E'}
}


def bfs(graph, start: str):
    result_map = defaultdict(int)

    visited = set()
    queue = deque([[start, 0]])

    while queue:
        v, depth = queue.popleft()
        visited.add(v)

        if v in graph:
            result_map[v] = depth

        for u in graph[v]:
            if u not in visited:
                queue.append([u, depth + 1])
                visited.add(u)

    return dict(result_map)


print(bfs(graph, 'A'))

Output:

{'A': 0, 'C': 1, 'B': 1, 'E': 2, 'D': 2, 'F': 3}