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 can be done to fix signal attenuation problems, What can be done to fi...

What can be done to fix signal attenuation problems? A common way of dealing with like problem is to use repeaters and hub, because it will help regenerate the signal and thus

Find the domain, Find the domain Name of 128.252.160.200

Find the domain Name of 128.252.160.200

Explain about the integrating intranet, Explain about the Integrating Intra...

Explain about the Integrating Intranet These Intranets are designed to replace the complexity of in-house communications and processing systems that large organisations ofte

Network, do you do paraphrase

do you do paraphrase

Explain what are the external threats, Explain what are the External Threat...

Explain what are the External Threats External security threats are the most problematic ones. Till date the greatest threat was the virus menace. Now, with the sophisticated

Use of a distance vector routing algorithm, Question: (a) The diagram ...

Question: (a) The diagram below shows a configuration of Internet routers (A-F) which achieve dynamic routing through the use of a Distance Vector routing algorithm. The metr

How firewall configuration makes all the difference, How Firewall configura...

How Firewall configuration makes all the difference The greatest blunder that any company make is to just install a firewall and think that they have ensured perfect securit

Explain about the gopher, Explain about the Gopher The ghoper is a prot...

Explain about the Gopher The ghoper is a protocol designed to search, retrieve and display documents from remote sites on the  Internet. The Ghoper was formed as a piece of sof

Define topologies other than basic topologies, What are the popular topolog...

What are the popular topologies other than basic Topologies? Apart from basic topologies some other topologies worth considering are: mesh topology (each device linked to all o

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