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

Network design, Get the network design for a company

Get the network design for a company

#title.assignment., hii i want to make a assignment from you. please help m...

hii i want to make a assignment from you. please help me.

Illustrate the drawbacks of stop and wait, Q. Illustrate the Drawbacks of s...

Q. Illustrate the Drawbacks of stop and wait? Drawbacks of stop and wait - Only one frame is able to be in transit at a time - After every frame sent the host must wai

Difficulties in internetwork communication, Q. Difficulties in Internetwork...

Q. Difficulties in Internetwork Communication? - Data arrive at interface f1 of s1 - How does s1 know that they must be sent out from interface f3? - There is no provisio

How can data to be exchanged between networks, Q. How can data to be exchan...

Q. How can data to be exchanged between Networks? Internetwork Links in an internetwork

Explain the building blocks of client and server, Explain the building bloc...

Explain the building blocks of Client/Server? The client side building block runs the client side of the application. The server side building block runs the server side of

What is the advantage of address sharing, What is the advantage of address ...

What is the advantage of address sharing? By using address translation instead of routing, address sharing gives an inherent security benefit. That's because host PCs on the In

Example on multiplicative decrease, Q. Example on Multiplicative Decrease? ...

Q. Example on Multiplicative Decrease? w = 1 for (each new ACK received) w = w+1 until (loss detected or w >= ssthresh) Not so slow - Exponential increase

Configure the management interface- spanning tree protocol, Configure the m...

Configure the management interface address on all three switches.  S1(config)#interface vlan1 S1(config-if)#ip address 172.17.10.1 255.255.255.0 S1(config-if)#no shutdown

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