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

LAN, what is man LAN wan

what is man LAN wan

Determine the value of slow start threshold, Assuming that TCP Reno is used...

Assuming that TCP Reno is used, consider the following diagram illustrating the behaviour of congestion window, and answer the questions below. a)  What was the value of sl

Function of tcp - ip transport layer, Q. Function of TCP/IP Transport Layer...

Q. Function of TCP/IP Transport Layer ? TCP/IP Transport Layer - Defines two standard transport protocols UDP and TCP - TCP equipment a dependable data-stream protocol

Explain stop--and--wait automatic repeat request, Q. Explain Stop--and--Wai...

Q. Explain Stop--and--Wait automatic repeat request? 1. Numbering frames prevents the retaining off duplicate frames. 2. Numbered acknowledgement are needed in case of delay

What automatic repeat request, What Automatic Repeat Request (ARQ)? Err...

What Automatic Repeat Request (ARQ)? Error control is both error detection and error correction. It allows the receiver to inform the sender of any frames lost or damaged in tr

Compute the number of lost packets of the down-stream, A mobile host (MH) i...

A mobile host (MH) is connected to a WLAN access network that uses MIP for mobility support. Consider that the RTTs between MH and HA are 0.3s while RTTs within a L2 subnet are 80

State about the future of the intranet, Future of the intranet At ...

Future of the intranet At present, the world of information technology is guided bythe C 3 paradigm that stands for Command, Control and Communication, which is normally

E-NRZ, A modified NRZ code known as enhanced-NRZ (E-NRZ) operates on 7-bit ...

A modified NRZ code known as enhanced-NRZ (E-NRZ) operates on 7-bit words; inverting bits 2,3,6 and 7; and adding one parity bit to each word. The parity bit is chosen to make the

Designing an internet work, 1. Introduction This document describes t...

1. Introduction This document describes the research-based assignment for this module. This assignment consists of two parts: A formal report And a presentatio

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