Dijkstra’s Algorithm for Distance and Shortest Paths in Weighted Graphs

Create a WeightedGraph class that is similar to your existing Graph class, except that now, each edge is assigned a value called a weight.

icon


Initialize the WeightedGraph with a weights dictionary instead of an edges list. The edges list just had a list of edges, whereas the weights dictionary will have its keys as edges and its values as the weights of those edges.


>>> weights = {
    (0,1): 3, (1,0): 3,
    (1,7): 4, (7,1): 4,
    (7,2): 2, (2,7): 2,
    (2,5): 1, (5,2): 1,
    (5,6): 8, (6,5): 8,
    (0,3): 2, (3,0): 2,
    (3,2): 6, (2,3): 6,
    (3,4): 1, (4,3): 1,
    (4,8): 8, (8,4): 8,
    (8,0): 4, (0,8): 4
}

>>> weighted_graph = WeightedGraph(weights)


In a weighted graph, the distance between two nodes is the sum of the weights on the shortest path between them. For example, the distance from node $8$ to node $4$ is $7$ because the shortest path is $8 \stackrel{4}{\to} 0 \stackrel{2}{\to} 3 \stackrel{1}{\to} 4.$

In particular, notice that the shortest path is NOT $8 \stackrel{8}{\to} 4$ because the distance along this path is $8.$


>>> [weighted_graph.calc_distance(8,n) for n in range(9)]
[4, 7, 12, 6, 7, 13, 21, 11, 0]

>>> weighted_graph.calc_shortest_path(8,4)
[8, 0, 3, 4]

>>> weighted_graph.calc_shortest_path(8,7)
[8, 0, 1, 7]

>>> weighted_graph.calc_shortest_path(8,6)
[8, 0, 3, 2, 5, 6]


The underlying algorithms for calc_distance and calc_shortest_path are a bit more complicated for weighted graphs than for unweighted graphs.

To implement calc_distance(from_idx, to_idx) we need to use Dijkstra’s algorithm, which works by assigning each node an initial guess for its distance and then repeatedly updating those guesses until they actually represent the distances to those nodes.

  1. When setting initial guesses, the "from" node is assigned a distance value of $0$, and all other nodes are assigned distance values of $\infty$ (just use a large number like $9999999999$).
  2. Set the current_node to be the "from" node.
  3. Loop through the current_node's unvisited children and update their distances as child.distance = min(child.distance, current_node.distance + edge_weight).
  4. Update the current_node to be the unvisited node with the smallest distance value (not necessarily a child node).
  5. If the ending node has not been visited yet, then return to step 3.
  6. Return the distance attribute of the "to" node.

Let’s demonstrate each iteration of Dijkstra’s algorithm when computing the distance from node 8 to node 6.

First, we set the initial guesses for the distance values. Since we’re starting at node 8, we already know that it’s a distance of $0$ from itself. All the other nodes get initial guesses of infinity.

icon


Now, we visit node 8 (the “from” node) and update the distance values on its children.

icon


The next node we visit should be the unvisited node with the smallest distance value. This would be node 0, whose distance value is $4.$ We visit this node and update the distance values on its unvisited children.

icon


Again, we visit the unvisited node with the smallest distance value. This time, it’s node 3.

Notice that when we update the distance values on its unvisited children, node 4’s distance value decreases from $8$ to $7.$ Whenever a distance value decreases like this, it means that the nodes we’ve traversed contain a shorter path than a path we found earlier.

In our first iteration, we found a path $8 \stackrel{8}{\to} 4$ with distance $8.$ Now, we found a path $8 \stackrel{4}{\to} 0 \stackrel{2}{\to} 3 \stackrel{1}{\to} 4$ with distance $7.$

icon


As usual, we visit the unvisited node with the smallest distance value. This time, we can visit either node 1 or node 4 (they are the unvisited nodes with the smallest distance values). We’ll arbitrarily choose to visit node 1 and update the distance values of its children.

icon


We keep on repeating this same procedure until the “to” node (node 6) has been visited.

icon


icon


icon


icon


icon


We’ve visited node 6, and its distance value is $21.$ This means that the distance from node 8 to node 6 is $21.$

But what is the specific shortest path from node 8 to node 6 that gives us this distance of $21?$

To find the shortest path, we first construct the shortest-path tree by discarding any edge (a,b) whose weight does not match the corresponding difference between distance values, b.distance - a.distance.

icon


Once we have the shortest-path tree, we’ve effectively reduced our problem down to a problem that we’ve already solved: finding the shortest path between two nodes in an unweighted graph.

icon


Indeed, we can see that the shortest path from node 8 to node 6 in the tree above is given by $8 \to 0 \to 3 \to 2 \to 5 \to 6.$ And indeed, in the weighted graph, the sum of weights along this path is $21.$

Leave a Comment