shortest path problem

Shortest path problem can be defined as a problem to find minimum distance between two vertices/nodes of connected weighted graph.Dijkstra’s algorithm is an efficient algorithm for finding shortest path in a connected weighted graph. for example in below graph the shortest path to reach from A to D is ACED because the total distance between A to D in this path is 9,  which is minimum if we travel from any other path or route from A to D.

Shortest_pathNote: To apply Dijkstra’s algorithm for finding shortest path following conditions need to be satisfied.

  • Graph ( directed or undirected ) must be connected.
  • All weights of edges must be positive. Dijkstra’s algorithm does not work with negative weight.

How Dijkstra’s algorithm works

The below is the steps of Dijkstra’s algorithm ( from Wikipedia.org).

  1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
  2. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
  3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example in above example, if the current node A is marked with a distance of 0, and the edge connecting it with a neighbor C has length 2, then the distance to C (through A) will be 0 + 2 = 2. If C was previously marked with a distance greater than 2 then change it to 2. Otherwise, keep the current value.
  4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
  5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
  6. Select the unvisited node that is marked with the smallest tentative distance, and set it as the new “current node” then go back to step 3.

  Example graph based on above steps:

dijk2

shortest path problem dijkstra’s algorithm sample code