The Algorithm

If you are not yet familiar with Dijkstra’s algorithm, start by looking at the example and its correction. Reading the algorithm first is not the easiest thing.

    
        Function: Dijkstra
Inputs: 
  - G = (A,S): a digraph without an absorbing cycle.
  - p: a function of arity 2 
  giving the weight of an edge in O(1)
  // Example p(1,2) gives the weight of the edge (1,2)
  - source: index of the source vertex
  
Outputs: 
  - pred: An array containing 
  for each vertex the chosen 
  predecessor.
  - weight: An array containing 
  for each vertex the total weight 
  (the sum of the weights) to traverse 
  to reach it from the source.
  
Start: 
  // Initialization
  For $s\in S$: 
    weight[s] <- inf
    preds[s] <- "-"
  EndFor
  weight[source] <- 0
  
  // Main body of the function
  Q <- S
  While $Q \neq \emptyset$: 
    // Start by searching 
    // minQ, the first vertex to validate
    temp <- inf
    minQ <- -1
    For $q \in Q$:
      If weight[q] < temp:
        temp <- weight[q]
        minQ <- q
      EndIf
    EndFor
    Q <- Q - {minQ}
    For each successor q' of q: // Or neighbor if the graph is undirected
      // If the recorded distance 
      // is greater than the distance of the predecessor 
      // + weight of the edge: 
      // Update the information of q'
      If weight[q'] > weight[q] + p(q,q'):
        weight[q'] <- weight[q] + p(q,q')
      EndIf
   EndFor
  EndWhile
End
    

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.

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:

Example 1

Example 2:

Example 2

Solutions

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).

Solution 2

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

Weight Table

Some hints to understand this table:

• At each step, we look at the vertex with the smallest associated weight and examine its successors. For example, at the step Q-=s, we look at the successors of s, and if they are closer than our recorded value, then we update the table. For instance, in column 0: 6<$+\infty$.
• “/” is just there for readability. The number above it is the real value of the cell.
• Q -= s means we remove the vertex s from Q. If you look at the algorithm, at the initialization of Q, we have Q = “All vertices”. For each iteration, we deal only with the vertices in Q, so at the step Q -= s, we have filled the column of 0
• Q -= 3 makes no change because among the successors of 3, we have 1. However, weight[1] = 4 which is equal to weight[3] + p(3,1) = 4. We make a change only if the new weight is strictly less than the recorded weight.
• After the step $Q -= 1$, we have 2 vertices of weight 6. The choice doesn’t really matter. Q being a set, it’s unordered, so let’s follow the lexicographic order arbitrarily.
• The table of predecessors below helps keep track of the path taken to reach the vertex. The 2 tables are filled simultaneously.

Predecessors Table

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:

$$s \rightarrow 1 \rightarrow 4 \rightarrow 5 \rightarrow 2 \rightarrow t$$

The total weight is: $4+2+1+1+3 = 11$