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

Prepare a lan from a set of stand-alone computers, Question 1: Describe...

Question 1: Describe the following terms in your own words: a. Internet b. WWW c. Intranet

Show the error correction by hamming code, Q. Show the Error Correction by ...

Q. Show the Error Correction by Hamming Code? Hamming Code is able to be applied to data units of any length and uses the relationship between data and redundancy bits For i

Explain how a cdma system works, (a) Explain how a CDMA system works? (b...

(a) Explain how a CDMA system works? (b) Explain howWelsh-Hadamard codes are generated. Explain why orthogonality between different spreading codes is important. (c) Consider

Describe mail access protocols, Q. Describe Mail Access Protocols? Mai...

Q. Describe Mail Access Protocols? Mail Access Protocols - Used by receiver to retrieve mail when desired - Post Office Protocol, version 3 (POP3) is a simple limited

Electronic mail - application layer, Electronic Mail One  of the  most...

Electronic Mail One  of the  most popular internet  services is electronic mail ( e mail). At  the beginning  of the internet era teh message sent by  electronic  mail were sh

Stop service advertisements from flooding a network, To stop Service Adver...

To stop Service Advertisements (SAPs) from flooding a network, Cisco routers do not forward them. How are services advertised to other networks? Ans) Every router builds its own

Vpn technology - point to point , VPN Technology For an organization  ...

VPN Technology For an organization  VPN  technology  uses some main  techniques for privacy a.Encryption /Authentication b.Tunnelling c.Fire walls

The internet layer - fundamentals of networks, The Internet Layer The ...

The Internet Layer The  internet  layer is  responsible  for routing the data  packets  to the appropriate  destination. Internet protocol (IP) is responsible for ensuring dat

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