Computing shortest path in a graph, Computer Networking

Assignment Help:

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.


Related Discussions:- Computing shortest path in a graph

What is meant by 3-tier architecture, In 3-tier Client/Server systems, the ...

In 3-tier Client/Server systems, the application logic (or process) lives in the middle tier and it is removed from the data and the user interface. In theory, the 3-tier Client/Se

Define interconnection network, Interconnection Network An interconnect...

Interconnection Network An interconnection network is designed for transferring data between two processors in a Multi-stage network. Memory bottleneck is a fundamental limitat

Distance-vector routing, Local information is immediate hop routing table a...

Local information is immediate hop routing table and distance from every switch. The switches regularly broadcast topology information i.e. distance, destination. Other switches mo

Show the bidirectional transmission, Q. Show the Bidirectional Transmission...

Q. Show the Bidirectional Transmission? Bidirectional Transmission Each party must maintain S and R to track frames sent and expected Piggybacking hooking ACK wit

Create a wireless can, You are the network administrator for the City of Jo...

You are the network administrator for the City of Joshua Texas. The city government offices are located in five buildings separated by a State Highway controlled by the State of Te

Source to destination data transfer - datagram approach, Source to Destinat...

Source to Destination Data Transfer - Datagram approach - Each packet is treated independently. - Every pkt will take its own path to reach the destination. - There i

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd