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 sonet, What is Sonet Synchronous Optical Network is a fiber opt...

What is Sonet Synchronous Optical Network is a fiber optic technology that can transmit high-speed data audio, used for text and video. Single clock handles timing of transm

What are the control frames for lost tokens, Control Frames for Lost Tokens...

Control Frames for Lost Tokens If station goes down ... token lost Predecessor listens for data frame or token Noticing none, retransmits token Sends whofoll

What is multistation access unit, Multistation Access Unit (MAU) C...

Multistation Access Unit (MAU) Combines individual automatic switches May perhaps daisy chain to support more stations

What is data storage technology, Normally, we think of communications scien...

Normally, we think of communications science as dealing with the contemporaneous exchange of information among distant parties. Though, many of the same techniques employed in data

Projecr assingment, I have a project that need to be submit as soon as poss...

I have a project that need to be submit as soon as possible

Line layer - sonet sdh , Line Layer The line layer provides the synchr...

Line Layer The line layer provides the synchronization multiplexer, multiplexing and automatic  protection switching for the layer . primary  concerned with the  reliable trans

What is a java package, What is a Java package and how is it used? A J...

What is a Java package and how is it used? A Java package is a naming context for classes and interfaces. A package is used to make a separate name space for groups of classes

Network, What are the main features of TCP connections? Why is it said that...

What are the main features of TCP connections? Why is it said that TCP provides full-duplex service?

Systolic array, Systolic Array This interconnection network is a kind o...

Systolic Array This interconnection network is a kind of pipelined array architecture and it is designed for multidimensional flow of data. It is used for executing fixed algor

Prompt ''router'', Recognize the mode reflected by the following prompt 'Ro...

Recognize the mode reflected by the following prompt 'Router '? Ans) RXBoot

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