Dijkstra’s algorithm

Searching the shortest path between two vertices is a very common problem when you are dealing with graphs. This problem can be solved by various algorithms and in this article I will try to describe Dijkstra’s algorithm DA. But first, I would like to show you a shortest path in an arbitrary graph.

sp_!

As you can see, the shortest path has minimal sum of all weights of its constituent edges. A path can occur in either directed or undirected graphs. Moreover, in directed graph it is possible situation that there are no path between two edges at all.

sp_2

The shortest path problem can have following variations:

  1. The single-source shortest path problem, in which we have to find shortest paths from a source vertex to all other vertices in the graph.
  2. The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex.
  3. The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices in the graph.

Dijkstra’s algorithm solves the single-source shortest path problem in directed graph with nonnegative weights.

Implementation

Let’s consider the example with a road map. One wants to go from city A to city H. On the diagram below vertices represent cities and edges represent roads.

da_1

As you can see, there are several ways to go. Some roads longer than others, but you need to choose only one way. So – one of the possible solutions is to apply DA to find the shortest path. For this, we need to store distance from starting city A to others. Initially, all cities have unknown distance (we can use infinity for this) and only city A has distance 0 (because distance from A to A is equal to 0).

Step 1:

da_2

Step 2:

In the next step, we are evaluating distance from city A to cities B, D and C (adjacent nodes). Distance between A and B is equal to 12, between A and D to 20, between A and C to 10.

da_3

Step 3:

In step 3, we are evaluating distance farther from nodes B, D and C to its adjacent nodes (B ->F, D->H, C->D, C->G). Distance from B to F is equal to 13. Since we are evaluating distance from starting node which is A, we need to add evaluated distance from A to B. So – we get 25 (A->B + B->F = 12 + 13 = 25). The same formula we are using to calculate distance from D to H, which is equal to 43. Distance from C to G is equal to 35. Distance from C to D is equal to 24 and this distance is greater than 20 (A->D). Thus, A->C->D is longer than A->D, and we choose path A->D and leave distance value as it is.

da_4

Step 4:

In step 4, we are evaluating distance from F to H and from G to H. Distance from F to H is equal to 34 and it is less than 43 (path A->D->H), so we can rewrite distance to 34. Distance from G to H is equal to 42 and it is greater than 34, and we won’t use this path.

da_5

Step 5:

This is the final step. Because, node H is our destination point and there are no ways to go. Therefore, we can complete our algorithm.

da_6

As result, we have the shortest distance from starting city to any other.

Basing on example above we can distinguish following steps of the algorithm:

Pre-conditions:

  1. Graph G=(V, E).
  2. Array D of size |V| for  storing distance values.
  3. Min heap H.
  4. Staring vertex v.

Algorithm:

  1. Add all vertices into the H (keyed by diastance).
  2. Set +∞ for all elements in D.
  3. Set D[v] equal to 0.
  4. If is not empty go to step 4.1, otherwise to step 5.
    1. Get minimum value from H.
    2. Remove from H.
    3. For each neighbour n of u do steps from 3.1 to 3.x. If there are no neighbours go to step 4.
      1. If D[u] + weight of edge u->v is less than D[v] then set D[v] = D[u] + weight of edge u->v.
  5. End.

Here goes java version of this algorithm: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/DijkstrasAlgorithm.java

Complexity

Time taken to build a minimum heap is O(V), time taken to remove minimum value from heap is O(log V). Also we have loop for all edge in the graph with complexity O(E). All together can be combined to O((V+E) log V).

Leave a Reply