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 the acknowledged connectionless service, Explain the Acknowledged c...

Explain the Acknowledged connectionless service This is a cross between the previous two services. It provides that datagrams are to be acknowledged, but no prior logical conne

Show the drawbacks of go-back-N, Q. Show the Drawbacks of Go-back-N? D...

Q. Show the Drawbacks of Go-back-N? Drawbacks of Go-back- N - Inefficient - Every out of order received packets are discarded (receiver side is simplified) - This

What is the purpose of configuration files for servers, Question 1: a) ...

Question 1: a) Give three examples of Shells in Linux. b) Differentiate between the Join command and the Paste command in Linux, use an example to support your answer.

Application of satellite communication , Application of Satellite Communica...

Application of Satellite Communication started with the installation and commissioning of STD- “B” Earth Station having 11m diameter antenna in 1982, Initially with to only three

State token ring implementation, Token Ring Implementation Sequence...

Token Ring Implementation Sequence of 150-ohm shielded twisted-pairs sections Output port on every station connected to input port on the next Frame is passed to

How to configure a wireless mac filter - ccna, Configure a Wireless MAC Fil...

Configure a Wireless MAC Filter Step: Add a Mac filter. Navigate back to the web utility page of the router (http://172.17.30.1). Navigate to the Wireless section a

Why do we require a subnet mask? , If the host has the subnet ID why do we ...

If the host has the subnet ID why do we require a subnet mask?

Explain radio wave, Explain Radio Wave. Although Radio waves are common...

Explain Radio Wave. Although Radio waves are common and well understood, we are just starting to realize their enormous potential as a networking medium. Radio waves can operat

Explain types of networking and internetworking device, What is the differe...

What is the different type of networking / internetworking devices? 1. Repeater: Also known as a regenerator, it is an electronic device that operates only at physical layer.

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