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 basic key functions of data link layer, Q. What are the basic ...

Q. What are the basic key functions of data link layer? Ans: Data link layer transfers data in a structured and reliable manner so that the service given by the physical layer

Describe the following topics, Describe the following topics A . LAN B . M...

Describe the following topics A . LAN B . MAN C . WAN D . ARPANET

What is a hypertext link, A hypertext link is a special tag that links sing...

A hypertext link is a special tag that links single page to another page or resource. If you click the link, the browser goes to the link's destination.

Cells vs packets, ATM designers select cells over packets because of the fo...

ATM designers select cells over packets because of the following facts: Cells are fixed length and memory management for them is easy. Handling variable length packets tends

Discuss about the latest internet and intranet technologies, Latest Interne...

Latest Internet and Intranet technologies Even though the security capabilities of the latest Internet and Intranet technologies have enabled the companies to control the avail

What is wan, What is WAN? A wide area network is defines a LAN o...

What is WAN? A wide area network is defines a LAN of LANs. WANs connect LANs that might be on opposite sides of a building, across the country or around the world.  WANS

Explain in brief about the term- daemon, What is Daemon A daemon is ...

What is Daemon A daemon is a UNIX background process that implements the server side of a protocol. Daemons are unique to UNIX. For example, FTP stands for the File Transfer

Briefly describe three security requirements of an agent, QUESTION (a) ...

QUESTION (a) Briefly describe three security requirements of an agent (b) List four threats that may be caused by malicious hosts to mobile agents (c) Describe the forwar

Explain the term - carrier sense multiple access, What is use of Carrier se...

What is use of Carrier sense multiple access Carrier sense multiple access with collision detection (CSMA/CD) is a form of medium access control in which a station listens to

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