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

When would we use isdn, We use IDSN supports high speed voice, data and vid...

We use IDSN supports high speed voice, data and video and is a good choice for many small businesses.

What are mac addresses, What are MAC addresses? MAC, or Media Access Co...

What are MAC addresses? MAC, or Media Access Control, uniquely identifies a device on the network. It is also called as physical address or Ethernet address. A MAC address is m

Uneven load distribution, Uneven Load Distribution In the parallel com...

Uneven Load Distribution In the parallel computer, the problem is dividing into sub-problems and is assigned for computation to various processors. But sometimes the sub-probl

Explain the two modes of ip security, Question 1 Describe the architecture...

Question 1 Describe the architecture and usage of ISDN Question 2 Write about different network structures in use Question 3 Explain the concept of framing in Data Li

Wlan technology, Identify and briefly explain any four key requirements tha...

Identify and briefly explain any four key requirements that need to be examined when considering deploying a WLAN technology.

What are the disadvantages of bus topology, What are the disadvantages of b...

What are the disadvantages of bus topology? The disadvantages of bus topology are: a. The bus networks are dissimilar to reconfigure, especially when the acceptable number o

Disadvantages of ip sec tunnelling mode, Disadvantages of IP sec  Tunnelli...

Disadvantages of IP sec  Tunnelling mode IP sec  tunnelling  mode has the  following  disadvantage a.Encryption of  small  packets  generates a lot  networks  over head  thu

Building a http server, IMPORTANT: The web server should be able to serve H...

IMPORTANT: The web server should be able to serve HTTP files only. You will not need to implement the directory listing and CGI-bin. Purpose The objective is to implement a H

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

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