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

Question

Both can be used to find the shortest path from single source. BFS runs in O(E+V), while Dijkstra's runs in O((V+E)*log(V)).

Also, I've seen Dijkstra used a lot like in routing protocols.

Thus, why use Dijkstra's algorithm if BFS can do the same thing faster?

Outpour

Answer 1

Dijkstra allows assigning distances other than 1 for each step. For example, in routing the distances (or weights) could be assigned by speed, cost, preference, etc. The algorithm then gives you the shortest path from your source to every node in the traversed graph.

Meanwhile BFS basically just expands the search by one “step” (link, edge, whatever you want to call it in your application) on every iteration, which happens to have the effect of finding the smallest number of steps it takes to get to any given node from your source (“root”).

Vercingetorix

Both will yield the same results i.e a path between two vertices, but only dijkstra will guarantee the shortest path. – Snapper

@jmcarter9t incidentally your comment seems to be the second comment of the accepted answer. But I assume you mean this comment – Hoeg

@Hoeg Thanks for the correction. Should be second comment of the accepted answer at the answer at this link: #25450281 – Conditioner

Answer 2

If you consider travel websites, these use Dijkstra's algorithm because of weights (distances) on nodes.

If you will consider the same distance between all nodes, then BFS is the better choice.

For example, consider A -> (B, C) -> (F) with edge weights given by A->B = 10, A->C = 20, B->F = C->F = 5.

Here, if we apply BFS, the answer will be ABF or ACF, as both are shortest paths (with respect to the number of edges), but if we apply Dijstra's, the answer will be ABF only because it considers the weights on the connected path.

Eno

Answer 3

Dijkstra's algorithm

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

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

Width

Answer 4

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

Source

Bloodstained

Is it true, though? Dijkstra revisits nodes if path's cost is smaller. BFS doesn't revisit nodes. So technically it's not exactly the same with sole difference of swapping queue with priority queue. – Atmospheric

That is not true, implementations are completely different. Dijkstra is starting from priority queue fully initialized with all vertices with and distance equal infinity except for the starting node. BFS is starting with a queue containing starting node. – Wendolyn

Answer 5

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))

Wendolyn

The variable cheapest is not defined here – Artur

Answer 6

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 or A->B->D->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}

Artur

Answer 7

• 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

Noami