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 silly window syndrome, Q. Explain Silly window syndrome? When e...

Q. Explain Silly window syndrome? When either sending application sends data gradually or receiving application consumes data slowly - Illustration when 1 byte sent 40 bytes

Framing, different framing methods

different framing methods

Nics and network hardware, NICs AND NETWORK HARDWARE:  NIC is create f...

NICs AND NETWORK HARDWARE:  NIC is create for one kind of physical network. For example Ethernet interface may not be needed with token ring and similar ATM interface cannot b

Describe a typical dns system, Question: (a) With the help of a diagra...

Question: (a) With the help of a diagram, describe a typical DNS system. (b) Using signal sequence or state transition diagrams, illustrate the following scenarios: i.

Enumerate about the star topology, Enumerate about the Star networks C...

Enumerate about the Star networks Comments: 1 - If one connection/station fails the other devices aren't affected 2 - If central hub breaks down, the whole network fail

Determine the rate of communication line, Determine the rate of communicati...

Determine the rate of communication line The dog could carry 21 gigabytes or 168 gigabits. A speed of 18 km/hour that is equal to 0.005 km/sec. The time to travel the distance

Network problems, Network Problems Q1  Consider the single-sender CDM...

Network Problems Q1  Consider the single-sender CDMA example in Kurose & Ross. What would be the sender's output (for the 2 data bits shown), if the sender's CDMA code were (

Hardware difficulty of benz network, Hardware difficulty of Benz Network: -...

Hardware difficulty of Benz Network: - Benz network uses smaller switches and it gives excellent connectivity.  To find hardware difficulty of Benz network let us presume that

Explain the acknowledged connectionless service, Explain the Acknowledged c...

Explain the Acknowledged connectionless service This is a cross between the previous two services. It provides that datagrams are to be acknowledged, but no prior logical conne

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