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

Repeater - network layer and routing, Repeater Repeater is  also named...

Repeater Repeater is  also named as active hub operates at physical  layer of OSI model. Repeater is an  electronic  device that simply regenerates the signal. Signals travell

Record route ip option, The address recorded by a router should be its outg...

The address recorded by a router should be its outgoing interface. That is, if a router forwards a datagram that has the record route option enabled, and if the datagram arrives at

System - network administrator, The program must be well documented which i...

The program must be well documented which includes meaningful variable and subroutine names ("self documenting code") along with comments in the code. The following block of code w

Explain the operation of a token ring topology for a lan, Question: (a)...

Question: (a) Show by means of a diagram the Ethernet frame structure and describe the six fields of the Ethernet frame structure. (b) Explain the operation of the Carrier S

What is wdm, What is WDM? WDM is conceptually the similar as FDM, excep...

What is WDM? WDM is conceptually the similar as FDM, except that the multiplexing and demultiplexing includes light signals transmitted by fiber optics channel.

What is bens network, Q. What is Bens Network? It's a non-blocking netw...

Q. What is Bens Network? It's a non-blocking network. It's a special type of Clos network where first and last stage consists of  2×2 switches (for n input  and m output networ

C, #questionWrite a program to find the area under the curve y = f(x) betwe...

#questionWrite a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two poi

Define the class B addresses, Define the Class B Addresses? First t...

Define the Class B Addresses? First two octets are the network number as well as the last two octets are the host number 16382 probable blocks for assignment to organi

Write the purpose of split horizon, Split Horizon - If you attain a protoc...

Split Horizon - If you attain a protocol's route on an interface, do not send information about that route back out that interface.

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