SKEDSOFT

Shortest Path Algorithm: In many areas like transportation, cartoon motion planning, communication network topology design etc, problems related to finding shortest path algorithms. The shortest path problem is concerned with finding the least cost (that costs minimum) path from an originating node in a weighted graph to a destination node in that graph. Let us consider a graph shown in the Fig. (4.1) in which number associated with each arc represent the weight of the arc.

There exist many algorithms for finding the shortest path in a weighted graph. One such algorithm is developed by Dijkstra in the early 1960’s for finding the shortest path in a graph with non-negative weight associated with edge/arc without explicitly enumerating all possible paths. This algorithm is based upon a technique known as dynamic programming.

This algorithm determines shortest path between a pair of nodes in a graph. If there are n nodes in a graph, we need to run the algorithm nC2 times. In a network of 100 or more nodes, the time taken to compute the shortest path for all possible pair of nodes can be any body’s guess.

To overcome this we shall discuss a modification of Dijkstra’s alogrithm to find shortest distance between one node to all other nodes in a graph and Floyd Warshall’s algorithm to compute all pair shortest path.