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

How many types of twisted pair cable are there, How many types of twisted p...

How many types of twisted pair cable are there We can find two types of twisted pair cables, namely: Unshielded Twisted Pair Cable (UTP) and Shielded Twisted Pair Cable (STP).

Explain the functions and features of the ipmonitor program, Functions and ...

Functions and features of the IPMonitor program are as follows:   a)  This program should be able to list out detail information of IP traffic which includes source IP address an

Root dns servers - application layer , Root DNS Servers A root  server...

Root DNS Servers A root  server is a serve which  consists of the entire  hierarchy  of servers. A root  server  usually  does not  store any  information  about  domains  but

How to configure vtp pruning on the switches-ccna, Configure VTP Pruning on...

Configure VTP Pruning on the Switches VTP pruning permits a VTP server to suppress IP broadcast traffic for particular VLANs to switches that do not have any ports in that VLAN

Timing in mpi program, MPI_Wtime ( ) returns elapsed wall-clock time in sec...

MPI_Wtime ( ) returns elapsed wall-clock time in seconds as some arbitrary point in past. Elapsed time for program segment is specified by the difference between MPI_Wtime values a

Briefly explain the terms ''cohesion'' and ''coupling'', QUESTION 1 (a)...

QUESTION 1 (a) Draw a use-case model for the above system. You must identify all possible actors and use-cases. (b) Assume you are using the Rational Unified Process a

Circuit switched networks, Question 1 Write about                       Ci...

Question 1 Write about                       Circuit Switched Networks                       Packet Switched Networks Question 2 Write about                       Protocol Indep

Show a simplex stop and wait automatic repeat request, Q. Show a simplex St...

Q. Show a simplex Stop and Wait automatic repeat request? A simplex Stop and Wait ARQ - Normal Operation - Frame lost - Acknowledgement lost - Acknowledgement de

What does the spanning tree algorithm (sta) do, IEEE 8021.d Spanning Tree P...

IEEE 8021.d Spanning Tree Protocol (STP) was developed to stop routing loops in a network. If a router, switch, or hub has more than one path to the similar destination, a routing

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