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 security risks present on the networks, Security risks present on the ...

Security risks present on the networks Lots of risks are present everywhere on Internet as well as on Intranet, if it is not known what is being done. Every day a number of

Configure the logical topology - configure router1, Configure Router1. ...

Configure Router1. From Host1, connect to the console of Router 1 and establish a console session. Directions for creating a console connection using HyperTerminal are in Appen

Message passing programme development environment, Message Passing Programm...

Message Passing Programme Development Environment In a multicomputer system, the computational load among various processors must be balanced. To pass information among variou

Receipt of acknowledgment - transport layer, Receipt of Acknowledgment ...

Receipt of Acknowledgment In our GBN  protocols  an acknowledgment for  packet with sequence number will be taken to be accumulative acknowledgment  indicating that all  packe

Define the term - graphics interchange format, Define the term - Graphics I...

Define the term - Graphics Interchange Format A type of graphics file found frequently on the .net. A picture of a vice-president, for example, may appear on the Intranet as

Set up to use pvm run and complie, PVM uses two environment variables when ...

PVM uses two environment variables when starting and running. Every PVM user needs to set these two variables to use PVM. The initial variable is PVM_ROOT, which is set to the loca

State the methods to keep the attackers at bay, State the methods to keep t...

State the methods to keep the attackers at bay Another best methods to keep the attackers at bay is known as network address translator or NAT. The philosophy behind the design

Show the character-level encryption, Q. Show the Character-level Encryption...

Q. Show the Character-level Encryption? - Substitutional - Monoalphabetic - simplest form; also called Caesar cipher - Every character is replaced with another character

Html, write a html program segment that contains hypertext links from one d...

write a html program segment that contains hypertext links from one document to anothersk question #Minimum 100 words accepted#

Tcp – numbering bytes, Q. TCP – numbering bytes? Numbering is utili...

Q. TCP – numbering bytes? Numbering is utilized for flow & error control Segments aren't numbered only bytes Full-duplex connection - numbering is independent in

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