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 classification of computer network by range, Question 1 Explain cl...

Question 1 Explain classification of computer Network by range Question 2 Explain three major problems of Transmission lines Question 3 What is the maximum data rate of

Determine the functioning of service support, Determine the functioning of ...

Determine the functioning of Service Support Service Support must be considered a strong point for hardware, especially for servers and should be available readily. Many brande

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?

traffic flow mapping , Develop traffic flow mapping and performance requir...

Develop traffic flow mapping and performance requirements for flows. A) Traffic Flow Mapping B) Performance Requirements

Factors effects the quality of image of monitor, Q. Factors effects the qua...

Q. Factors effects the quality of image of monitor? Four factors effects the quality of image of monitor:   1.  Phosphor coating: This affects the colour and persistence (Th

Bridges, BRIDGES:  A bridge is a hardware device also needed to connec...

BRIDGES:  A bridge is a hardware device also needed to connect two LAN code segments to extend a LAN. A bridge uses two NICs to connect two code segments. It listens to all tr

What is transmission media, Q. What is Transmission Media? - Actually s...

Q. What is Transmission Media? - Actually situated below the physical layer - Directly controlled through the physical layer - Data should be converted into electromagnet

What are intrusion detection systems, Question : a) Give three example...

Question : a) Give three examples of vulnerable services which are among the overwhelming majority of successful attacks. b) Name the five outside sources which can be the

Encryption authentication - point to point , Encryption Authentication ...

Encryption Authentication One common  technique  used to encrypt and authenticate in VPNs is IP security. IP sec  is a collection of protocols designed by the IETF( Internet En

Which type for communication switch do, In case of any new event switch do ...

In case of any new event switch do broadcast, after that always do Unicast.

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