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 is forest, The term "forest" is used to explain a collection of AD dom...

The term "forest" is used to explain a collection of AD domains that share a one schema for the AD. All DC's in the forest share this schema and it is replicated in a hierarchical

Illustrate transport layer responsibilities, Q. Illustrate Transport Layer ...

Q. Illustrate Transport Layer Responsibilities ? - Process-to-process delivery of whole message - Port addressing - Segmentation and reassembly - Connection control co

What are the data units at different layers of the tcp, What are the data u...

What are the data units at different layers of the TCP / IP protocol suite? The data unit formed at the application layer is known as a message, at the transport layer the data

Case study, #questi Scenario: Your Case Study must be based on the informat...

#questi Scenario: Your Case Study must be based on the information provided. There will be no additional information. This must be submitted in a .doc, or .pdf format. If you sen

Explain the term instruction pipelines, Instruction Pipelines The strea...

Instruction Pipelines The stream of instructions in instruction execution cycle may be realized by a pipeline where overlapped executions of various operations are performed. T

Thread libraries, The most difficult representatives of shared memory progr...

The most difficult representatives of shared memory programming models are thread libraries present in mainly of the modern operating systems. Some examples for thread libraries ar

Advantages of ls over dv algorithm, Advantages of LS over DV algorithm ...

Advantages of LS over DV algorithm There  are a number of advantages to link  state  protocols  especially when  compared to  the distance vector based  routing  protocols. The

Unused reserved - trannsport layer, Unused Reserved This  is a 6 bi...

Unused Reserved This  is a 6 bite field  reserved for future use.

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

Transmission control protocol, Transmission Control Protocol (TCP) TCP ...

Transmission Control Protocol (TCP) TCP makes the Internet reliable. TCP solves several problems which can occur in a packet switching system. TCP provide the given facilities:

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