Shortest Path Routing (static)

The idea of this shortest path routing is simple, which is used to build a graph with each node as router and arc represents a communication line (or) link.

This algorithm just finds the shortest path between them on the graph.

There exists many design metrics to choose to get the shortest path are no.of hops, queue length,transmission delay etc.

for example if we choose no.of hops as metric, the paths ABC, ABE have equal no of hops means that those are equally long but ABC is much larger than ABE.

The labels on the above graph (2,2,7) are computed as a function of the distance, Band width, average traffic, cost etc.

one of the algorithm used for computing the shortest path between 2 nodes is Dijkstra’s algorithm.

it is as follows, Initially all nodes are labeled with infinite distance.

Let us consider the figure as shown below

to find the shortest path from A to D.

step 1:- choose the source node as A and mark it as permanent node.

step 2:- find the adjacent nodes to A  those are B and G then choose the node with the smallest label as the permanent node.

Now this node B becomes the new working node.

step 3:- Now start at B and repeat the same procedure

by following above procedure two paths are available ABEGHD with a distance of 11 from A and ABEFHD with a distance of 10 from A.

so the second path is chosen as a shortest path.

therefore the final shortest path is ABEFHD with nodes A,B,E,F,H and D as permanent nodes.

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)


Author: vikramarka

Completed M.Tech in Digital Electronics and Communication Systems and currently working as a faculty.