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

Broadcast and multicast , Broadcast and Multicast : Broadcast and Mult...

Broadcast and Multicast : Broadcast and Multicast :In the broadcast interconnection network, at one time one node transfer the data and all other nodes get that data.  Broadca

Brdging between buildings, BRDGING BETWEEN BUILDINGS:  If two building...

BRDGING BETWEEN BUILDINGS:  If two buildings are placed far from each other, a bridge, a pair of fiber modems and an optical fiber may be used to locate two LANs as given in t

Describe the method of one way redistribution and mutual, Define  the conce...

Define  the concept of one way redistribution and mutual

What is authentication, Q. What is Authentication ? - Verification of s...

Q. What is Authentication ? - Verification of sender's identity. - Accomplished through a digital signature, which is based on public key encryption/decryption. - Uses re

Ip message finally reassemble, Concept of how does the IP message finally r...

Concept of how does the IP message finally reassemble?

Critical path method, You are the Senior Project Manager in a software comp...

You are the Senior Project Manager in a software company and have, as part of your team, a student on a three month internship. The student has proudly told you that they have stu

How to protect computer hardware by threats, How to protect computer Hardwa...

How to protect computer Hardware by threats The first component in the computer system vulnerable to attacks or threats, and most important to be protected, is the hardware.

Discuss about the similarity of intranets to the internet, Discuss about th...

Discuss about the similarity of Intranets to the Internet The ease of use of the end user would be the most noticeable because of the similarity of Intranets to the Internet. S

What is the purpose of a default route, A default route is used if there is...

A default route is used if there is not a particular entry in the routing table for the destination.

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