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

Determine the task which should intranet require, Determine the task which ...

Determine the task which should intranet require Intranet to work smoothly, the following tasks should be properly synchronised: All computers connected together in a n

Describe about domain name space, Q. Describe about Domain Name Space ? ...

Q. Describe about Domain Name Space ? - Structure for systematize the name space in which names are defined in an inverted-tree structure with the root at the top - Every l

Describe encapsulating, Can you describe encapsulating, carrier and passeng...

Can you describe encapsulating, carrier and passenger protocol?

Networking device, what is the best time to use brouter rather than router?...

what is the best time to use brouter rather than router? what are advantages of using brouter over router?

Show the routing table, Q. Show the Routing Table? Routing Table ...

Q. Show the Routing Table? Routing Table Every router remains a routing table that has one entry for every destination network of which the router is aware Proces

Routing table - network layer and routing , Routing Table Each  router ...

Routing Table Each  router now  uses the  shortest path tree to construct its routing table . each  router  uses the same algorithm and the same link state  database its own sh

What is raid in ccna, A method used to standardize and categorize fault-tol...

A method used to standardize and categorize fault-tolerant disk systems. RAID levels give lot of mixes of performance, reliability, and cost. Some servers give three of the RAID le

Explain dynamic key management mechanism, Question: a) Consider the f...

Question: a) Consider the following MIP scenario. Quite a few enterprise networks use private addresses and NAPT for the communication to the Internet. i. Discu

Working of internet, As discussed in the earlier section each computer link...

As discussed in the earlier section each computer linked to the Internet has a unique address. Let's assume your IP address is 1.2.3.4 & you wish to send a message to the computer

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