The path finding problem has received considerable attention in the
past. Many algorithms have been devised for it's solution. Dijkstra's
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
This algorithm solves the problem in
steps by using a binary heap, 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
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.
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.
Dijkstra's Algorithm applied to the network of Figure 1.
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 ALGORITHMSM.Abaidullah ANWAR 1999-11-25