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

Access networks and physical media - computer network, Access Networks and ...

Access Networks and Physical Media Access  networks  are the  physical  links(S) that connect  an end  systems to its edge  router. Which  is the  first router on a path  fr

Objective of parallel algorithms, After studying this part the students wil...

After studying this part the students will be able to understand about the following: Analysis of Parallel Algorithms; Different Models of Computation; o   Interco

Point to point architecture - application layer, Point to Point Architectur...

Point to Point Architecture The term  peer means equal which can  be informally  interpreted as a process with  capability similar to the other processes with process communic

Describe in detail with example how data fragmentation works, Describe in d...

Describe in detail with example how data fragmentation works?

State sonet frame, SONET Frame Can be viewed as a matrix of nine rows ...

SONET Frame Can be viewed as a matrix of nine rows of 90 octets every for a total of 810 octets.  A few used for control they aren't positioned at the beginning or end of the

Configure spanning tree- ccna, Configure Spanning Tree Step 1: Ex...

Configure Spanning Tree Step 1: Examine the default configuration of 802.1D STP. On each switch, display the spanning tree table with the show spanning-tree command. R

Error and flow control in dll, differntiate between error control and flow...

differntiate between error control and flow control in data link layer

What is telnet, What is Telnet It is a protocol or set of rules that us...

What is Telnet It is a protocol or set of rules that uses to connect one computer to another computer in network. It is also called as a remote login. The telnet operates on cl

Describe the method of one way redistribution and mutual, Define  the conce...

Define  the concept of one way redistribution and mutual

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