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

Light sources and connectors, - Light source is LED (light-emitting diode) ...

- Light source is LED (light-emitting diode) or a laser - LEDs are cheaper however not as precise (unfocused) limited to short-distance use - Lasers is able to have a narrow

What is proxy serer and firewall, What is Proxy Sever and Firewall Pro...

What is Proxy Sever and Firewall Proxy Sever Also known as a proxy or application level gateway. It is an application that breaks the connection among sender and receiver.

Agent management system, QUESTION (a) Figure 3 below shows a reference ...

QUESTION (a) Figure 3 below shows a reference model of the Foundations of Intelligent Physical Agents (FIPA). Explain the roles of the following components (i) Agent platfor

Define co-axial cable, Define Co-axial cable. A solid central conducto...

Define Co-axial cable. A solid central conductor surrounded by insulating material and then by a cylindrical shield woven from fine wires is called as co-axial cable. The shie

Show about alternate mark inversion, Q. Show about Alternate mark inversion...

Q. Show about Alternate mark inversion? Bipolar AMI - Neutral, zero voltage represents binary 0 - Binary 1s symbolized by alternating positive and negative voltages

Explain semantic web , What the Semantic Web is? Ans) The Semantic Web ...

What the Semantic Web is? Ans) The Semantic Web is a vision, that thinks to join together dispersed bits of data on the internet, very much like web pages are presently joined

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

Routing in a wan, As there will be more devices there will be more traffic ...

As there will be more devices there will be more traffic of information. We can include capacity to WAN by adding more links and packet switches. Packet switches use not have compu

frames along with the rtp, For VOIP, first you need to consider the codec ...

For VOIP, first you need to consider the codec to use. Although there are many voice codecs, MyCo wants the safest bet and suggests that you design with the most known and oldest c

Find the main problems with access points in a wireless lan, Question: ...

Question: Wireless Access points have been known to have various security vulnerabilities that can lead to breach of Secured wired networks. IEEE 802.11 standards have identifi

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