Is Dijkstra's Algorithm just BFS where you also tally node weights?

Question

For an online course I had the assignment to implement Dijkstra's Algorithm. I completed the algorithm as described, where you maintain lists of explored and unexplored nodes and update their unexplored neighbor's distance scores as you traverse the graph (and move nodes to the explored list).

I noticed that this looks a lot like bread first search so I tried modifying BFS to update node scores as nodes are added to the queue. This seems to work exactly the same but without tracking what nodes are in the explored vs unexplored queues explicitly.

Is this just a matter of implementation details? Are these both examples of Dijkstra's algorithm or is one different?

Dijkstra example:

def dijkstra(graph, source):
    explored_set = set()
    all_nodes = set(graph.keys())
    node_distances = create_distance_dict(graph)
    node_distances[source] = 0
    while explored_set != all_nodes:
        current_node = min_distance(node_distances, explored_set)
        explored_set.add(current_node)
        update_distances(graph, node_distances, current_node)
    return node_distances

def min_distance(distances_dict, explored_set):
    """ Helper function returns lowest distance node not yet explored """
    minimum = float("infinity")
    for node in distances_dict.keys():
        if node not in explored_set and distances_dict[node] <= minimum:
            minimum, min_index = distances_dict[node], node
    return min_index


def update_distances(graph, distances_dict, current_node):
    """ Helper function updates neighbor's distances """
    for n in graph[current_node]:
        if distances_dict[n[0]] > distances_dict[current_node] + n[1]:
            distances_dict[n[0]] = distances_dict[current_node] + n[1]

bfs based search example

def search(graph, source, nodeDistances):
    nodeDistances[source] = 0
    queue = deque([source])
    while len(queue) != 0:
        n = queue.popleft()
        for m in graph[n]:
        # Iterate each node connected to n
            if m and nodeDistances[m[0]] > nodeDistances[n] + m[1] :
            # Compare current m score and update if n + n-m edge is shorter
                nodeDistances[m[0]] = nodeDistances[n] + m[1]
                # add m to search queue
                queue.extend([m[0]])

    return nodeDistances

Graph and nodeDistances structure used for both examples:

nodeDistances = {
    1: 0,
    2: float("infinity"),
    3: float("infinity"),
    4: float("infinity"),
    5: float("infinity"),
    6: float("infinity"),
    7: float("infinity"),
    8: float("infinity"),
    }
graph = {
    1: [(2,1),(8,2)],
    2: [(1,1),(3,1)],
    3: [(2,1),(4,1)],
    4: [(3,1),(5,1)],
    5: [(4,1),(6,1)],
    6: [(5,1),(7,1)],
    7: [(6,1),(8,1)],
    8: [(7,1),(1,2)],
}

Dijkstra's algorithm is nothing but BFS which uses priority queue instead of normal queue. — Shreyash S Sarnayak, Mar 25 '17 at 19:35
@ShreyashSSarnayak Nope, BFS assesses one step at a time, whereas Djikstra's algorithm assesses weighted edges. They are not the same thing — the_constant, Mar 25 '17 at 19:40
@NoticeMeSenpai Please take a look at [wikipedia page](https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue) — Shreyash S Sarnayak, Mar 25 '17 at 19:42
@ShreyashSSarnayak please take a look at: http://stackoverflow.com/questions/3818079/why-use-dijkstras-algorithm-if-breadth-first-search-bfs-can-do-the-same-thing — the_constant, Mar 25 '17 at 19:47
@NoticeMeSenpai A generic BFS does that. But this is modified where he is checking for updated distance `nodeDistances[m[0]] > nodeDistances[n] + m[1]`. This will give shortest path. — Shreyash S Sarnayak, Mar 25 '17 at 19:52
@ShreyashSSarnayak take a look at my answer and it'll make more sense. There is no such thing as "a generic BFS". Either it's a BFS, or it's not. — the_constant, Mar 25 '17 at 19:57
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/139050/discussion-between-shreyash-s-sarnayak-and-notice-me-senpai). — Shreyash S Sarnayak, Mar 25 '17 at 19:58

score 3 · Answer 1 · edited May 23 '17 at 12:02

3

The short answer is: no, Dijkstra's algorithm is not a Breadth First Search.

As explained in this Stack Overflow post: Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?,

Dijkstra's algorithm analyzes weighted edges of a graph, meanwhile a BFS analyzes the shortest distance one step at a time.

Take for example the following graph (not to scale):

        10
  A --------- B 
5  \          |
    C -- D    |
       3  \   | 10
           \  |
         8  \ |
             E

In the above, a BFS will find that the shortest path from A to E is A -> B -> E, which is true for the number of steps. However, Dijkstra's Algorithm will find that the shortest path from A to E is A -> C -> D -> E, because of the weight of the edges of the graph.

The distance for the BFS from A to E is 20 units, whereas the shortest distance via Dijkstra's Algorithm from A to E is 16.

edited May 23 '17 at 12:02

Community

1
1

answered Mar 25 '17 at 19:56

the_constant

681
4
11

1

Yes I understand this. I guess my question was more in reference to the modified BFS I showed in the original post where the algorithm updates the smallest distances between connected nodes as the BFS traverses the graph. – Solomon Bothwell Mar 25 '17 at 20:13
I know this is old, but for anyone new here. Consider there were more node connected to Node E in the above graph. The BFS algorithm would start exploring node E in time (t) = 2. But later BFS would realize that - "Oh shit! We could have reached node E in smaller units at time (t) = 3sec". So it will again add the node E in queue and start exploring futher again. This will shoot up the runtime and time complexity of algorithm depending on the graph. Hence, Dijkstra's is much better here. – Aryan Shridhar Feb 11 '22 at 12:02

score 1 · Answer 2 · answered Mar 25 '17 at 20:21

The algorithm you have written is Single source shortest path.

Dijkstra's algorithm is nothing but SSSP where we use priority queue instead normal queue.

The only difference it makes is the number of times a node is visited.

n = queue.popleft()
for m in graph[n]:
    if m and nodeDistances[m[0]] > nodeDistances[n] + m[1] :
        nodeDistances[m[0]] = nodeDistances[n] + m[1]
        queue.extend([m[0]])

In Dijkstra we just update the priority (distance) which make it visit sooner. There will be only one entry for a node in proirity queue.

In SSSP you might be adding the node to queue multiple time after it's neighbour gets updated making it update multiple times and making its neighbour update by adding it to the queue.

Is Dijkstra's Algorithm just BFS where you also tally node weights?

2 Answers2