Dijkstra’s algorithm

Before we understand Dijkstra algorithm, let’s introduce the concept of graph. A graph consists of vertices and edges connecting them. A graph has many applications because it mimics the connection between nodes/ vertices in network, social media, map with buildings as nodes and roads as edges connecting them, etc.

Dijkstra algorithm is an algorithm to find the shortest path from a source vertex to a destination vertex in a graph. For example, the graph may be a map. This is useful because a person may want to drive from home to school using the shortest path possible.

Each edge/ “road” is given a value, this is the path cost or the cost to travel this particular road. The shortest path will have the lowest sum of path costs of the edges it travelled.

There may be variations for the implementation of Dijkstra algorithm. For any implementations, each vertex will have a current cost which is continually updated until it reaches the minimum.

Implementation

To start, we have two sets, S, and N. S contains the vertices that have been processed and N contains the vertices that have not. Initially, S is {} and N is {a, v1, v2, v3, v4, v5, v6, z}.

In Iteration 0, set the current cost of the source vertex as 0 and the current cost of the rest of vertices to a very big value, that is, infinity.

Note: Keep track of current cost of all vertices as we will update the current cost of certain vertices of all vertices during each iteration. For now, after iteration 0, one vertex has 0 as current cost and the rest has infinity as current cost.

In Iteration 1, select the vertex from N that has the lowest current cost and move to S. Then, we will update the current cost of neighbours of the vertex we chose. The new currenct cost of the neighbours will be updated by adding the currenct cost of the vertex we chose, and the path cost from the vertex chosen and the neighbour itself.

Note: We only update the current cost of neighbour to new currenct cost if it is lower than its current cost. Example, we chose v4, v5 is one of the neighbours of v4, the current cost of v5 is 15, the updated current cost of v5 is the current cost of v4 plus the path cost from v4 to v5, 12 + 6 = 18. Since 18 is more than 15, we don’t update the current cost of v5 to 18.

Note: When choosing a vertex from N that has the lowest current cost, sometimes there are two or more vertices with the same currenct cost in N, choose whichever one will do.

Subsequent iterations are the same as Iteration 1.

We continue the iterations until the destination vertex is moved to set S. The current cost of the destination vertex is the shortest distance from source vertex to destination vertex.

Example implementation: https://gist.github.com/shaunlgs/861276b2ff0ba49dc0eb1f3cf10accd0

Note: The graph information is stored in a matrix where the row and column are the vertex and the value is the path cost. Example, row 1 (The row are indexed from 0, so row 1 is actually the second row) and column 3, this means from v1 to v3, the path cost is 8.

Leave a Reply