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

What are the unix-based firewalls, What are the Unix-based firewalls T...

What are the Unix-based firewalls The Unix-based firewalls are considered most secured as compared to the Windows NT based ones. The firewalls bind the holes of the operating

Compute the number of lost packets of the down-stream, A mobile host (MH) i...

A mobile host (MH) is connected to a WLAN access network that uses MIP for mobility support. Consider that the RTTs between MH and HA are 0.3s while RTTs within a L2 subnet are 80

What are the key elements of protocols, What are the key elements of protoc...

What are the key elements of protocols? The key elements of protocols are a. Syntax   It refers to the structure or format of the data that is the order in which they a

Name some common or popular databases, Name some common or popular database...

Name some common or popular databases Many of the popular databases also provide support of and to the middleware and consequently, the term middleware has become lesser known.

Concept of connection between the pc and the cable modem, Concept of connec...

Concept of connection between the PC and the cable modem Even if downstream channel works at 27 Mbps, user interface is nearly always 10-Mbps Ethernet. There is no way to get b

Multi tasking environment, Multi Tasking Environment Multi tasking exp...

Multi Tasking Environment Multi tasking exploits parallelism by: 1)  Concurrently using the multiple functional units 2)  Pipelining functional units are pipe line toget

Multiplexing and de multiplexing, Multiplexing  and De multiplexing An...

Multiplexing  and De multiplexing Another  critical set of services that are provided by the transport layer is that of application multiplexing and de multiplexing. This featu

Calculate the voltage on the capacitor, Quetion: A 22 nF capacitor is i...

Quetion: A 22 nF capacitor is initially charged to 10V. It is then discharged by connecting a 100kW resistor across it. Approximately how long does it take for the voltage on t

Explain the transport layer in detail, Explain the transport layer in detai...

Explain the transport layer in detail Transport Layer: Transport layer ensures and controls the end-to-end integrity of data message propagated via the network  amid two devic

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