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("\nFrom
root %ld\n", 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\n", k, NextHop[k]);
printf("Printing
paths\n");
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).
No comments:
Post a Comment