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

Host system in tcp-ip model, Q. Host System in TCP-IP model? - Standard...

Q. Host System in TCP-IP model? - Standards adopted because of widespread use like (Internet) - The protocols came first plus the model was really just a description of the

Define what is a software agent, QUESTION (a) Define what is a software...

QUESTION (a) Define what is a software agent? (b) An intelligent agent is known to exhibit several characteristics or properties that distinguish it from another piece of so

What is the function of the osi session layer, What is the function of the ...

What is the function of the OSI Session Layer? This layer gives the protocols and means for two devices on the network to communicate with each other by holding a session.  Thi

Mail access protocols - application layer, Mail Access Protocols The e...

Mail Access Protocols The e mail  message  are usually  sent to  an email  server that stores received message  in the  recipient   e mail  mailbox.  The user  retrieves messa

TCP for live video, 1. What advantages and disadvantages does TCP have for ...

1. What advantages and disadvantages does TCP have for live video teleconferencing applications

Sketch the output waveform square wave that symmetrical, Question: The ...

Question: The input to the circuit in the figure is a square wave that is symmetrical about 0V. Sketch the output waveform.

Destination port number - transport layer, Destination Port Number Thi...

Destination Port Number This is  port number used by the process  running on the destination host. It is also 16 bits long  if the destination  host if  server ( a client  sen

Local and wide area networking, A. Current setting A new bank has its he...

A. Current setting A new bank has its headquarters located in City A. Recently, the bank has opened its first branch in City B, and its data centre in City C. The three cities a

Critical path method, You are the Senior Project Manager in a software comp...

You are the Senior Project Manager in a software company and have, as part of your team, a student on a three month internship. The student has proudly told you that they have stu

Networking concepts and applications, iLab 2: Office Network Expansion ...

iLab 2: Office Network Expansion Connect to the iLab here. Submit your assignment to the Dropbox located on the silver tab at the top of this page. (See "Due Da

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