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

Assigment, what the domain name of 128.252.160.2000

what the domain name of 128.252.160.2000

What are the access methods used in lan, What are the Access methods used i...

What are the Access methods used in LAN: i. Switched access: It is used in LANs which are assigned around CBXs. Electronic switching is techniques are used to provide access

Network performance measured by delay and throughput, Q. Network performanc...

Q. Network performance measured by delay and throughput ? delay versus load Delay is composed of? Throughput v/s network load

Determine the maximum output current, A logic gate drives a load, which has...

A logic gate drives a load, which has a resistance of 1 kÙ and a capacitance of 20 pF. The printed circuit track connecting the gate to its load has an 40 pF capacitance to ground.

Explain the term standard error, Question: a) What is a Linux shell? ...

Question: a) What is a Linux shell? b) Prepare the commands for the following tasks: i) Change the working directory ii) Show the working directory iii) Execute a pro

Explain the network allocation vector, Network Allocation Vector Timer ...

Network Allocation Vector Timer which shows how much time must pass before a station is allowed to check the channel

What is the meaning of p-persistent, What is the meaning of P-persistent ...

What is the meaning of P-persistent If the medium is idle, transmit with probability p, and delay one time unit with probability (1 - p); if the medium is busy, continue to lis

What is a file server, What is a File server? File servers are helpful ...

What is a File server? File servers are helpful for sharing files across a network. With a file server, the client passes requests for file records over system to file server.

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