Next: Knowledge-based Techniques Up: SHORTEST PATH ALGORITHMS Previous: SHORTEST PATH ALGORITHMS

## 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 steps by using a binary heap[7], where is the number of arcs and is the number of nodes in a network.

Let be the distance (sum of link weights along a given path) from source to a node . Let be the given cost between nodes and . There are two parts of the algorithm: An iniatialization step and a step to be repeated until the algorithm terminates:
1. Iniatialization. Set . For each node not in , set . We use for nodes not connected to . Any number larger than the maximum cost or distance in the network will suffice.
2. At each subsequent step. Find a node not in for which is a minimum and add to . Then update for all nodes remaining that are not in by computing

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

Table 1: Dijkstra's Algorithm applied to the network of Figure 1.
 Initial {1} 10 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.

Next: Knowledge-based Techniques Up: SHORTEST PATH ALGORITHMS Previous: SHORTEST PATH ALGORITHMS
M.Abaidullah ANWAR
1999-11-25