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

Compare error detection and error correction, Compare Error Detection and E...

Compare Error Detection and Error Correction: The correction of errors is more difficult than the detection. In error detection, checks only any error has happened. In error co

IPV6, is DVMRP multicast prtocol supports IPV6?

is DVMRP multicast prtocol supports IPV6?

Explain what a digital signature is and how it works, Question: a) Out...

Question: a) Outline the concept of the Real Time Gross Settlement (RTGS) system in Mauritius and name the three main system components of the MACSS. b) Differentiate bet

Programming based on data parallelism, Programming Based on Data Parallelis...

Programming Based on Data Parallelism In a data parallel programming model, the focus is on data distribution. Every processor works with a portion of data. We shall discuss on

Explain anti-aliasing techniques, Question: (a) Explain the issue assoc...

Question: (a) Explain the issue associated with vertices when the scan line scan line polygon fill algorithm is being applied? (b) Explain the logic of shortening edges to a

Switching creates variable latency through the switch, DEFINITION: Latency ...

DEFINITION: Latency = Delay. Because a store and forward switch reads the entire frame before forwarding, a larger frame takes longer than a shorter frame.

Residential access - computer network, Residential Access Residential ...

Residential Access Residential  access is connecting home  end  systems ( typically a PC but increasingly a home network) into the network. One form  of residential  access  i

State the types of performance of computer hardware, State the types of per...

State the types of performance of computer hardware The hardware, i.e., the server or computer has a direct relationship on performance in the following areas: Reliabili

Message passing programming, Message passing is probably the most extensive...

Message passing is probably the most extensively used parallel programming paradigm today. It is the mainly natural, portable and efficient approach for distributed memory systems.

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