**SHORTEST PATH**

** **An algorithm that is designed essentially to find a path of minimum length between two specified vertices of a connected weighted graph

· Initialize the array smallest Weight so that smallest Weight[u] = weights[vertex, u].

· Set smallest Weight[vertex] = 0.

· Find the vertex, v, that is closest to vertex for which the shortest path has not been determined.

· Mark v as the (next) vertex for which the smallest weight is found.

· For each vertex w in G, such that the shortest path from vertex to w has not been determined and an edge (v, w) exists, if the weight of the path to w via v is smaller than its current weight, update the weight of w to the weight of v + the weight of the edge (v, w).

**NS2 CODE FOR SHORTEST PATH ROUTING**

**DIJIKSTRA’S ROUTING ALGORITHM**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | int main() { Node N0(0); Node N1(1); Node N2(2); Node N3(3); Node N4(4); RoutingVec_t NextHop; RoutingVec_t Parent; N0.AddAdj(1, 10); N0.AddAdj(2, 5); N1.AddAdj(3, 1); N1.AddAdj(2, 2); N2.AddAdj(4, 2); N2.AddAdj(1, 3); N2.AddAdj(3, 9); N3.AddAdj(4, 4); N4.AddAdj(0, 7); N4.AddAdj(3, 6); Nodes.push_back(&N0); Nodes.push_back(&N1); Nodes.push_back(&N2); Nodes.push_back(&N3); Nodes.push_back(&N4); for (nodeid_t i = 0; i < Nodes.size(); i++) { // Get shortest path for each root node printf(" From root %ld ", i); Dijkstra(Nodes, i, NextHop, Parent); PrintParents(Parent); for (unsigned int k = 0; k < Nodes.size(); k++) printf("Next hop for node %d is %ld ", k, NextHop[k]); printf("Printing paths "); for (nodeid_t j = 0; j < Nodes.size(); j++) { PrintRoute(i, j, Parent); } } return(0); } |

**Different ways to identify shortest path routing in ns2**

- Transmission and propagation delays.
- Queuing delays.
- Minimum number of hops.

The optimal path is obtained through three steps, which is reverse route calculation in route request (RREQ), reverse route calculation in route reply (RREP) and reverse route calculation in route error (RERR). Experiments have been carried out using network simulator (NS2) and the obtained results are performed better than reactive routing protocol (AODV).

CLICK HERE TO VIEW MORE DETAILS