Why do we need Dijkstra's algorithm if this simpler, faster algorithm works?

user_10688867 0
Viewed 287

I have an an algorithm that iterates via BFS the whole graph, and it will update the score to find the min values to all nodes. And I believe the runtime complexity of this is O(V+E), which I believe is better than Dijkstra. Now obviously I'm not naive enough to actually think this algorithm is correct. However, I'm curious in which case, this would not find the optimal min path. here is the code I have

from queue import Queue

ad_list = {
    'A': {'B': 1, 'D': 3},
    'B': {'A': 1, 'D': 1, 'C': 5},
    'D': {'A': 3, 'B': 1, 'C': 3},
    'C': {'B': 5, 'D': 3}
}

min_weights = {
    'A': 0,
    'B': float('inf'),
    'C': float('inf'),
    'D': float('inf'),

}


def fake_dijkstra(ad_list):
    queue = Queue()
    queue.put('A')

    visited = {}

    global min_weights

    while not queue.empty():
        key = queue.get()

        # update score
        children = ad_list[key]

        for child_key, value in children.items():
            if min_weights[child_key] > min_weights[key] + value:
                min_weights[child_key] = min_weights[key] + value

        if key in visited:
            continue

        visited[key] = True

        children = ad_list[key]

        for child_key, value in children.items():
            queue.put(child_key)


fake_dijkstra(ad_list)
print(min_weights)

# for this case, it correctly finds the min weight to all nodes
{'A': 0, 'B': 1, 'C': 5, 'D': 2}

Any feedback would be highly appreciated. I love algorithms :).

dijkstra graph-algorithm graph algorithm
3 Answers

Your algorithm is not O(|V|+|E|).

Consider a fully connected graph G(V,E), where each node is connected with every other node.

In your algorithm, you are adding each node of such a graph to the queue |V-1| times, the startnode is added to the queue |V| times. Thus, the total number of elements ever been on the queue is |V| x |V-1| + 1

For each element of the queue, you are iterating over all of its |V-1| children for checking the minimum weight.

Thus the total number of of steps is |V| x |V-1| x |V-1| which is of course O(|V|³)

Depending on the data structure used for the queue, Dijkstra's algorithm ranges from O(|V|² + |E|) down to O(|V| x log |V| + |E|). For a fully connected graph |E| = |V|², thus Dijkstras algorithm is O(|V|²)

So it seems your algorithm can find the shortest paths for a given graph (I'm not 100% sure, but couldn't find a counter example). But it's not a typical BFS, because you are reevaluating the children of a node multiple times. That's also the difference to Dijkstra's algorithm. Because at the time, the children of a node X are evaluated (ie you take the step from X -> Y), it's guaranteed, that there is no shorter path from A to X. Thus, it's in a lower O-complexity

user_37769270

In unweighted graphs, a BFS is indeed the right tool to get distances. However, in weighted graphs, where edges have different lengths, it fails. Construct yourself a graph where there are two paths from a node s to a node t: one path with few nodes, and heavy edges, the other (shorter) one with many nodes and light edges. See what your algorithm does.

user_46941240

Consider this graph:

 A --- 5 --> B --- 1 --> C --- 1 ---> D
 |           ^
 |           |
  
 1           1

 |           |
 v           |
 E --- 1 --> F

The shortest path from A to D is found by going A -> E -> F -> B -> C -> D for a total distance of five. However, your algorithm is not guaranteed to find this. Imagine the following happens:

First, we process node A. This marks the distances to B and E as 5 and 1, respectively, and enqueues B into the queue, then E. The queue is now [B, E].

Next, we process node B. This marks the distance to C as 6 (B is at distance 5, plus the 1 from the edge), then enqueues C into the queue. The queue is now [E, C].

Next, we process node E. This marks the distance to F as 2 (E is at distance 1, plus the 1 from the edge), then enqueues F. The queue is now [C, F].

Next, we process node C. This marks the distance to D as 7 (C is at distance 6, plus the 1 from the edge), then enqueues D. The queue is now [F, D].

Next, we process node F. This marks the distance to B as 3 (F is at distance 2, plus the 1 from the edge), then enqueues B. The queue is now [D, B].

Next, we process node D. This has no effect. The queue is now [B].

Next, we process node B. This changes the distance of node C to be 4 (B is at distance 3, plus the 1 from the edge). However, the queue is not updated, since B has already been processed.

At this point, we're done. But notice that the distance to D is wrong - we set D to be at distance seven, but the real distance is five. Why is this? It's because when we revisited B along the path A -> E -> F -> B of distance 3, we'd already processed B assuming its distance was 5, and now that we've realized that the distance to B is lower we don't get a chance to follow all the paths from B again to see what happens. We do update C, which is immediately adjacent to it, but not D, which isn't adjacent to B.

Dijkstra's algorithm avoids this by not expanding out C until it has finished looking at the path from A -> E -> F -> B and realizing that the original guess on C was incorrect. That's why it's important to process nodes in order of the estimated cost rather than in a regular breadth-first order.

user_5015570
Related