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

Compare udp and tcp, QUESTION a) National regulations require the avail...

QUESTION a) National regulations require the availability of the following services for all IP to PSTN, PSTN to IP, and IP to IP calls. Name any three types of these features

Determine the command to disable cdp on an interface, Router(config-if)# no...

Router(config-if)# no cdp enable is the  command to disable CDP on an interface

Computer Information Systems, I am taking a computer information systems cl...

I am taking a computer information systems class for which I have an online test I need done. It will not let me attach all the material that is on the test but someone well versed

Explain 10base2 - thinnet, 10Base2 - Thinnet Cable diameter is abou...

10Base2 - Thinnet Cable diameter is about 0.64 cm (RG-58) More flexible as well as easier to handle and install than Thicknet "2" represents a maximum segment len

Compute the entropy of the source, A statistical encoding algorithm is bein...

A statistical encoding algorithm is being considered for the transmission of a large number of long text files over a public network. Part of the file content is as follows: DOD

What are the categories of traditional ethernet, Categories of traditional ...

Categories of traditional Ethernet a)  Baseband - digital signals using Manchester encoding b) 10Base2, 10-Base-T, 10Base5, 10Base-FL c)  First number signifies data rate

Lan- wan network module expansion slot, WAN interface card(WIC) slots T...

WAN interface card(WIC) slots Two fixed WIC slots are present in  2600 series router except 2691. It has contained 3 WIC slots. Network Module Expansion Slot( NM) slot

State the difference between byte streams and message, State the difference...

State the difference between Byte streams and message Byte streams and message are different. In a message stream, network keeps track of the message boundaries. In a byte stre

Calculate the total latency, a) Consider that a host is sending a frame of ...

a) Consider that a host is sending a frame of 1200 bytes to another host found 20 Kilometers away. (Assume that switching delay is negligible) i) Calculate the total latency (

Explain the concept of fragmentation, Fragmentation - Wireless environm...

Fragmentation - Wireless environment is very noisy - Corrupt frames must be retransmitted - Large frames must be divided into smaller ones to increase efficiency

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