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
Unbound Transmission Media Unbound transmission media extend beyond the limiting confines of cabling. They give a good communication alternative for WANS. The lack of physical

Explain the Physical layer The Physical layer of the OSI model sets standards for sending and receiving electrical signals among devices. It explains how digital data (bits) ar

IGRP is a distance vector routing protocol designed by Cisco. The maximum hop count is 255, and it uses a combination of variables to verify a composite metric. IGRP has an adminis

Q. Show the Drawbacks of Go-back-N? Drawbacks of Go-back- N - Inefficient - Every out of order received packets are discarded (receiver side is simplified) - This

Q. Illustrate Go Back - N protocol? Go Back - N - Sender window size - Receiver window size = 1 - Why the names go back- N? - When the frame is spoilt the sende

Disadvantages of OSPF protocol i) Single Area ii) High Hardware Requirements iii) Troubleshooting

Q. How is computer networks used in teleconferencing? Teleconferencing: Teleconferencing allows conference to happen without the participants being in the same place. Applica

What is the difference between trigger and rule? Ans) The triggers are known as implicitly by database generated events, whereas stored procedures are known as explicitly by cli

Briefly write functionalities of different OSI layers? The OSI Reference Model includes seven layers. Basic functionality of each of them is as follows: 1. Physical Layer:

CHARACTERIZATION OF NETWORKS:  There are three kinds of characterization of networks. LOCAL AREA NETWORK (LAN):  It is needed for a single building. METROPOLOTAN AREA