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

Functions and significance of tcp header’s fields, Describe the functions a...

Describe the functions and significances of all fields (such as Source Port and Destination Port) of a TCP header. Functions and significance of tcp header's fields FIELDS

Show the network layer duties, Network layer duties Internetwork ...

Network layer duties Internetwork - Physical and Data link layers are jointly responsible for data delivery on the network from node to node

Functions of the information security steering committee, Question: (a)...

Question: (a) Do you agree with the following statements (specify your reasons to support your answer for each):- i) Policies are the foundation for the development of sta

What is wan, What is WAN? A wide area network is defines a LAN o...

What is WAN? A wide area network is defines a LAN of LANs. WANs connect LANs that might be on opposite sides of a building, across the country or around the world.  WANS

Name three agent development toolkits, QUESTION (a) Name two properties...

QUESTION (a) Name two properties of an agent (b) List the three characteristics used to classify agents according to the Nwana Taxonomy (c) Agent environments can be clas

Explain about error detection, Q. Explain about Error Detection? Data c...

Q. Explain about Error Detection? Data can be corrupted during transmission because of accidents, Storms, sudden increase in electricity and voltage / decrease in signal power

What is a dedicated server, What is a dedicated server? A network serve...

What is a dedicated server? A network server designated to provide one particular service is known as dedicated server. For example if a computer is assigned for database servi

Mpi functions and environment, MPI contains hundreds of functions, a small ...

MPI contains hundreds of functions, a small subset of which is enough for most practical purposes. We shall talk about some of them in this unit. Functions for MPI Environment:

State briefly about fddi media, FDDI Media Class B or SAS (single-attac...

FDDI Media Class B or SAS (single-attachment stations) attach to one ring Class A or DAS (dual attachment stations) attach to both rings. SASs is attached to the primary rin

Explain the authentication header (ah) protocol, Can you explain the Authen...

Can you explain the Authentication Header (AH) Protocol?

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