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 is aspects of security, Q. What is Aspects of Security? - Securit...

Q. What is Aspects of Security? - Security Attack: Any action whichcompromises the security of information owned by an organization. - Security Mechanism: A mechanism th

Determine the maximum number of stations, (i)  Suppose N stations are conne...

(i)  Suppose N stations are connected to an extended Ethernet LAN, as shown below shown in Figure operating at the rate of 10 Mbps. Assume that the efficiency of each Ethernet is 8

Describe the term - certification authority, Describe the term - Certificat...

Describe the term - Certification Authority The certification is most easily implemented with a custom solution combined with a server, called the Certification Authority (CA).

Calculate the amplifier''s gain in db, Quetion: An amplifier increases ...

Quetion: An amplifier increases the peak-to-peak voltage of a signal from 1 V to 20 V. What is the amplifier's gain in dB?

What are called fat clients and fat servers, If the amount of the applicati...

If the amount of the application runs on the Client side, then it is Fat clients. It is mostly used for decision support and personal software. If the amount of the application

Protocols are used for logical network addressing, Which of the following p...

Which of the following protocols are used for logical network addressing? Ans) Internet Protocol - IP gives routing and a one interface to the upper layers. No upper layer proto

Horizontal scaling and vertical scaling, What is meant by horizontal scalin...

What is meant by horizontal scaling and vertical scaling? Ans) Horizontal scaling means adding or removing client workstations with only a small performance impact. Vertical

What is authentication, Q. What is Authentication ? - Verification of s...

Q. What is Authentication ? - Verification of sender's identity. - Accomplished through a digital signature, which is based on public key encryption/decryption. - Uses re

Output port - network layer and routing , Output Port The function of t...

Output Port The function of the  port is  take  the packets that have  been stored in the out  put port  memory and transmits them over the out going  link. The queuing  and bu

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