SPIRO THE TECH GURU

Back

What is Shortest path?

By Admin on

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


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


SPIRO Google Plus