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

Explain design issues of interconnection network, Design Issues Of Intercon...

Design Issues Of Interconnection Network Below are the issues, which must be considered when designing an interconnection network. 1)  Size and Dimension of network:  It m

Describe the term - stateful implies, Describe the term - stateful implies ...

Describe the term - stateful implies The term stateful implies that the firewall is wakeful and is capable of remembering the state of each session of packet exchange across it

Define the term - store-and-forward and cut-through switch, Store-and-forwa...

Store-and-forward switch  The layer 2 switch accepts a frame on an input line, buffers it briefly, and then routes it to the appropriate output line. Cut-through switch

Error detection and correction, Error detection and correction The digi...

Error detection and correction The digital traffic stream of second generation systems also lends itself to the use of error detection and correction methods. The result can be

What is smtp, What is SMTP? SMTP is short for Simple Mail Transfer Proto...

What is SMTP? SMTP is short for Simple Mail Transfer Protocol. This protocol deals with all internal mail, and gives the essential mail delivery services on the TCP/IP protocol

Illustrate network layer in osi layers model, Q. Illustrate Network Layer i...

Q. Illustrate Network Layer in osi layers model? Network Layer :  This is responsible for addressing messages and data so they are sent to the required destination, and for tr

Which layers are network support layers, Which layers are network support l...

Which layers are network support layers? a. Physical Layer b. Data link Layer and c. Network Layers

Minimum possible response time , Consider the similar conditions as the las...

Consider the similar conditions as the last problem, except for the following: what's the minimum possible response time for the 1 Gbps and a 1 Mbps line?  What does the diffrentia

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