While calculating shortest path, first we assume graph presentation of network at every node then we use Djikstra's algorithm to calculate shortest path from every node to other one. Then extract next hop information from giving path information and add next hop information into routing tables.

WEIGHTED GRAPH

Djikstra's algorithm will add weights on edges in graph. The shortest path is then the path with minimum total weight. It could be noticed that the shortest path is not necessarily with fewest edges. For example as given in the figure below:

The minimum path in the diagram from node 2 to node 6 is 2 to 3 and 3 to 6 as this way has the minimum weight so it is the shortest path.

DISTANCE MATRICS

Weights on graph nodes denote cost of traversing edge. This cost can be in time, hop or dollars counting (weight == 1). The resulting shortest path can not have fewest hops.

Posted Date: 7/31/2012 7:00:00 AM | Location : United States

Ask an Expert

Related Discussions:- Computing shortest path in a graph, Assignment Help, Ask Question on Computing shortest path in a graph, Get Answer, Expert's Help, Computing shortest path in a graph Discussions

Write discussion on Computing shortest path in a graph
Your posts are moderated

Write your message here..

Related Questions

Describe voluntary and compulsory tunnels, Can you describe voluntary and c... Can you describe voluntary and compulsory tunnels?

How do we continuously ping an ip address, How do we continuously ping an I... How do we continuously ping an IP Address?

Network performance & characteristics, There are two kinds of characteristi... There are two kinds of characteristics in case of network performance. Delay Throughput

Framing, different framing methods different framing methods

Maths, the equation x3-6x+9x-5=0 the equation x3-6x+9x-5=0

Shortest path tree and minimum-spanning tree, We studied Dijkstra's link-st... We studied Dijkstra's link-state routing algorithm for computing the unicast paths that are individually the shortest paths from the source to all destinations. The union of these

Firewall architectures-screening router, Screening Router In this setu... Screening Router In this setup network router acts as a firewall. It checks all incoming and outgoing packets according to the predefined rules. This filter is placed at the c

Transmission, definition definition

Sonet frame format - sonet sdh, SONET Frame Format SONET  uses  a basic... SONET Frame Format SONET  uses  a basic  transmission  rate of STS -1 that  is equivalent to 51.84 mbps. Higher level  signals  are integer multiples of the base rate. For  exa

Describe rsvp, Can you describe RSVP? Can you describe RSVP?