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 data units at different layers of the tcp, What are the data u...

What are the data units at different layers of the TCP / IP protocol suite? The data unit formed at the application layer is known as a message, at the transport layer the data

Features of transmission control protocol, The major features of TCP are fo...

The major features of TCP are following: Reliability : TCP ensures that any data sent by a sender arrives at the destination as it was sent. There cannot be any data loss or mo

Network devices - network layer and routing , Network Devices a.Hub ...

Network Devices a.Hub b.Repeater c.Bridge d.Gateway e.Switch f.Router Connecting devices can  classified  into networking and internetworking  devices when

Tp-lite and tp-heavy monitors, What are TP-Lite and TP-Heavy Monitors? A...

What are TP-Lite and TP-Heavy Monitors? Ans) TP-Lite is simply the integration of TP Monitor functions in the database engines.TP-Heavy are TP Monitors which handles the Client/

Ethernet cable, what is max length of cable I can use

what is max length of cable I can use

Advantages of fiber optics, Q. Advantages of Fiber Optics? - Higher ban...

Q. Advantages of Fiber Optics? - Higher bandwidth in comparison to twisted-pair and coaxial cable is not limited by medium but by equipment used to generate and receive signals

Explain about multiplicative decrease, Q. Explain about Multiplicative Decr...

Q. Explain about Multiplicative Decrease ? Multiplicative Decrease (MD) if a time-out take places the threshold is set to one maximum segment size (TCP Tahoe, TCP Reno).

What is kerberos in networking, What is Kerberos in Networking? It is a...

What is Kerberos in Networking? It is an authentication service developed at the Massachusetts Institute of Technology. Kerberos uses encryption to stop intruders from discover

The concept of universal service, The major problems with multiple networks...

The major problems with multiple networks are as given: A computer attached to a given server can only interact with other computers attached to the similar network.

Network Topology, What are the different types of network topologies

What are the different types of network topologies

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