Robin Pourtaud - Personal Blog
Dijkstra's Algorithm - Example and Correction
Dijkstra's Algorithm - Example and Correction
Dijkstra's algorithm is a shortest path search algorithm between a source and all other vertices in a graph without negative weights.
By Robin Pourtaud on

The Algorithm

Recommendation

If you are not yet familiar with shortest path algorithms, you should start with a bit simpler algorithm like the Bellman-Ford algorithm. You can find an explanation of the Bellman-Ford algorithm here.

def dijkstra(G: Graph, p:function(int,int) -> int, source: int) -> [prev: List[int], weight: List[int]]:
    '''Pseudo code of Dijkstra.

    Args: 
        G : Graph : A graph without negative cycles
        p : function(int, int) -> int : A function that returns the weight of the edge (u, v) in O(1). Example p(1,2) gives the weight of the edge (1,2)
        source : int : The index of the source vertex in V
    
    Returns:
        prev : List[int] : An array containing the predecessor vertex of each vertex.
        weight : List[int] : An array containing, for each vertex, the weight of the shortest path (sum of weights) from the source to this vertex.
    '''

    # Initialization
    for v in G.vertices:
        weight[v] = inf
        prev[v] = '-'

    weight[source] = 0 # From the source to the source, the weight is 0

    Q = G.vertices # All vertices

    while Q != {}: # While Q is not empty
        temp = inf
        minQ = -1
        for q in Q:
            if weight[q] < temp:
                temp = weight[q]
                minQ = q
        Q.remove(minQ)
        for q_prime in G.successors(minQ):
            if weight[q_prime] > weight[minQ] + p(minQ, q_prime):
                weight[q_prime] = weight[minQ] + p(minQ, q_prime)
                prev[q_prime] = minQ

    return prev, weight

Positive Weights Only

This algorithm only applies to graphs with positive weights! If your graph contains negative weights (but no negative weight cycles), you can use the Bellman-Ford algorithm.

Be aware that the complexity of Bellman-Ford is , while Dijkstra’s algorithm is or with a priority queue.

Here is a simple example of a graph where Dijkstra’s algorithm does not apply:

Diagram

Dijkstra would chose chose the path A to C of weight 1 since the weight of B is 4. But the shortest path is A to B to C of weight -1.

Example

Here are 2 digraphs (directed graphs).

  1. Can you use Dijkstra’s algorithm on these graphs to find the shortest path from s to t?
  2. If so, determine the shortest path from s to t using Dijkstra’s algorithm.

Example 1:

Diagram

I appologize for the edges crossing each other, the placement is automatic.

Solution 1

An edge in the graph is associated with a negative weight. Therefore, Dijkstra’s algorithm does not apply here. You should use the Bellman-Ford algorithm (or another).

Example 2:

Diagram

Solution 2

You can combine the 2 tables if you prefer, for example by putting in each cell “weight/pred”.

Weight Table

Stepss012345t
Init0
Q -= s/642
Q -= 3/64/
Q -= 1/6//6
Q -= 0///9/6
Q -= 4///9//7
Q -= 5///8///
Q -= 2///////11
Q -= t////////

Some hints to understand this table:

  1. Initialization: First we only know that the source vertext is at distance 0 from itself. The rest is unknown, so we put .
  2. Next steps: From the known vertices (here only the source), we look at the successors of the vertex with the smallest weight. We set the distance to the successor if it is less than the recorded value. Please write don’t forget to update the predecessors table at the same time.
  3. Q -=: We remove the vertex with the smallest weight from Q. Here, for this step, we remove the vertex s.
  4. Hint for readability: If the vertex is not in Q anymore, we put a ”/” in the cell. The number above is the real weight of the vertice.
  5. End of the algorithm: When Q is empty, we finally can read the last weight of .

Predecessors Table

Stepss012345t
Init--------
Q -= s/ss-s---
Q -= 3/ss-/---
Q -= 1/s/-/1--
Q -= 0///0/1--
Q -= 4///0//4-
Q -= 5///5///-
Q -= 2///////2
Q -= t////////

Let’s find the shortest path from S to T:

  • t’s predecessor is 2
  • 2’s predecessor is 5
  • 5’s predecessor is 4
  • 4’s predecessor is 1
  • 1’s predecessor is t

The shortest path from s to t is therefore:

The total weight is: