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
@ShreyashSSarnayak Nope, BFS assesses one step at a time, whereas Djikstra's algorithm assesses weighted edges. They are not the same thing — the_constant
@ShreyashSSarnayak please take a look at: stackoverflow.com/questions/3818079/… — the_constant
@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

the_constant the_constant · Accepted Answer · 2017-03-25T19:56:24

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.

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

2 Answers