Computing shortest path in a graph, Computer Networking

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:

2244_weighted graph.png

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







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
Related Questions
Point out the drawbacks of Token Ring. Few of the drawbacks of Token Ring are: a. Token Ring is very costly. All topology components cost much more than other more popular s

Computer Networks 1. Write about different network structures in use. 2. Explain the architecture and usage of ISDN. 3. Describe the concept of framing in Data Link Layer

What are the important topologies for networks? BUS topology: In this every computer is directly linked to primary network cable in a single line. Advantages: Inexpensive,

Q. Show the Network Layer Responsibilities? - Source-to-destination delivery it is possibly across multiple networks - Logical addressing - Routing

After going through this part, you should be capable to: Describe the concepts of message passing programming; List out the various communication modes for communication

What are the main categories based on which applications of computer network can be categorized? The major areas under which the applications for computer network can be divide

There are basically two functions for creating routing tables, which are as given: Manual entry Software Further there are two types for computing routing table inf

Difference between synchronous tdm and statistical tdm


Recognize the command to show the Frame Relay map table Ans) Router# show frame-relay map is the the command to show the Frame Relay map table