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

Analysis of the ethical issue, This ICT-related issue that has been raised ...

This ICT-related issue that has been raised in the contemporary media, and the article is required to be included as part of the essay: Undertake further research about this top

Define the distance vector routing, Q. Define the Distance Vector Routing? ...

Q. Define the Distance Vector Routing? Distance Vector Routing Every router periodically shares its knowledge about the entire internet with its neighbours Sharing

Two types of transmission technology , What are the two types of Transmissi...

What are the two types of Transmission Technology available in ccna? Ans) Point - to - Point and Broadcast are the Two types of Transmission Technology available in CCNA

What are the local network security issues, Q. What are the Local Network S...

Q. What are the Local Network Security Issues? Local Network Security Issues Password Protection - Encrypted username & password Group/Owner ID's - File Permissi

Show scalability and reliability of computer network, How do you account fo...

How do you account for higher scalability and reliability of computer network? Ans: Computer network will have a large number of computers, which can share database, software

What are local variables, What are local variables? Local varaiables ar...

What are local variables? Local varaiables are those which are declared within a block of code like methods. Local variables should be initialised before accessing them.

Distant vector protocols, RIP and IGRP are Distance Vectoring protocols tha...

RIP and IGRP are Distance Vectoring protocols that send their whole routing tables to their neighbours. In some Cisco literature, EIGRP is listed as an 'advanced distance vector

Describe various mail protocols, Question 1 Describe the following a. Inte...

Question 1 Describe the following a. Internet Technologies b. Networks c. Media Access Control Question 2 Explain the various classes of networks Question 3 Describe various m

What does a metric of 16 hops showwhen using RIP , Destination unreachable ...

Destination unreachable Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

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