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 how snmp works, Question: a) One of the most important duties ...

Question: a) One of the most important duties of a system administrator is to protect the information that is stored on network servers. In the same context, describe both Ma

Implement a transport layer protocol to transmit data, In this project, you...

In this project, you will implement a Transport Layer protocol to transmit data with Reliable Data Transfer from a client to a server in the presence of channel errors and loss. Th

Give the structure of an atm uni cell header, a) Consider a hypothetical a...

a) Consider a hypothetical arrangement of ‘self-learning' bridges shown in the figure below. Assuming all are initially empty, give the forwarding tables for each of the bridges B

FlowCharts, How do I draw a flowchart and psuedocode that allows the user t...

How do I draw a flowchart and psuedocode that allows the user to input two different values and complete the sum and display the results?

What is bipolar encoding, Q. What is Bipolar Encoding? - Uses three vol...

Q. What is Bipolar Encoding? - Uses three voltage levels negative, positive and zero - Zero level represents binary 0; 1s are represented with alternating positive and negat

Packet processing on vpn router, Consider the site-to-site VPN scenario sho...

Consider the site-to-site VPN scenario shown in Figure 2. Let's deploy the AH protocol on the two VPN routers so that no desktop on the two sites need to do any AH operations. Assu

Define guided media, Q. Define Guided Media? - Offers a conduit from on...

Q. Define Guided Media? - Offers a conduit from one device to another - Signal is directed as well as contained by physical limits of medium - Twisted-pair and coaxial ut

Packet switching and virtual circuit packet switching, Describe Circuit swi...

Describe Circuit switching, Packet switching and Virtual Circuit Packet switching. Explain their suitability for different applications such as telephone and internet. Packet S

Illustrate the model for network security, Q. Illustrate the Model for Netw...

Q. Illustrate the Model for Network Security? - A message is transferred from one party (Principal) to another. - A logical information channel is founded between the t

Mechanical characteristics of RS232 interface, Q. Mechanical Characteristic...

Q. Mechanical Characteristics of RS232 interface? - 9-pin connector - 9-pin connector is more usually found in IBM-PC but it covers signals for asynchronous serial com

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