Dijkstra's Algorithm

The path finding problem has received considerable attention in the past. Many algorithms have been devised for it's solution. Dijkstra's algorithm is perhaps the earliest and also one of the most efficient algorithm for the problem. Most of the others are variations of it. It can solve the route finding problems without any additional helping informations.
This algorithm solves the problem in $O( (\vert A\vert + \vert N\vert)log\vert N\vert )$ steps by using a binary heap[7], where $\vert A\vert$ is the number of arcs and $\vert N\vert$ is the number of nodes in a network.

Let $D(v)$ be the distance (sum of link weights along a given path) from source $s$ to a node $v$. Let $l(v, w)$ be the given cost between nodes $v$ and $w$. There are two parts of the algorithm: An iniatialization step and a step to be repeated until the algorithm terminates:

1. Iniatialization. Set $N = \{ s \}$. For each node $v$ not in $N$, set $D(v) = l(s, v)$. We use $\infty$ for nodes not connected to $s$. Any number larger than the maximum cost or distance in the network will suffice.
2. At each subsequent step. Find a node $w$ not in $N$ for which $D(w)$ is a minimum and add $w$ to $N$. Then update $D(v)$ for all nodes remaining that are not in $N$ by computing

   $D(v) := min[D(v), D(w) + l(w,v)]$

   Step 2 is repeated until all nodes are in $N$. The application of this algorithm to the network of Figure 1 is demonstrated by successive steps in Table 1 where $1$ is a source node and $5$ is destination node.

Table 1: Dijkstra's Algorithm applied to the network of Figure 1.

	$N$	$D(2)$	$D(3)$	$D(4)$	$D(5)$
Initial	{1}	10	$\infty$	30	100
1	{1,2}	10	60	30	100
2	{1,2,4}	10	50	30	90
3	{1,2,4,3}	10	50	30	60
4	{1,2,4,3,5}	10	50	30	60

Although Dijkstra's algorithm can solve route finding problems alone, but in a complex road network with thousands of roads and cross points it will take a long time to find the shortest path for the algorithm. It is also very wasteful in terms of computation. The reason is that it is not always necessary to search through the whole network in order to find the solution. For example, if someone wants to find a route with source and destination nodes in a city then it is not necessary to search the whole road network. But, a search in that city road sub-network will produce a solution. The Dijkstra's algorithm can also produce the solutions that are not suitable for human users as the shortest path may use many minor roads as part of the solution.