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

Define the term pipelined processor, Pipelined Processor A pipeline pro...

Pipelined Processor A pipeline processor can be described as a processor which comprises of a series of processing circuits known as segments and a stream of operands (data) is

Show the congestion avoidance in tcp, Q. Show the Congestion avoidance in T...

Q. Show the Congestion avoidance in TCP? Slow Start (SS) & Additive Increase (AI) (AI=Congestion Avoidance) start with the congestion window (cwnd) = max segment si

Deadlock avoidance or prevention, Deadlock Avoidance To avoid deadlock...

Deadlock Avoidance To avoid deadlocks two types of strategies are used: 1) Static prevention: It uses V and P operators and Semaphores to allocate and deallocate shared res

What is applets, What is Applets Little programs that can make the We...

What is Applets Little programs that can make the Web pages more aesthetically beautiful by means of animations, text, and graphics moving across the screen.

Explain the terms - lan extension and ad hoc network, Explain the terms - L...

Explain the terms - LAN extension and Ad hoc network LAN extension: a wireless LAN integrated with a wired LAN to extend the coverage area of the LAN complex; Cross-building

Define network, Communication, Resource sharing and Media (When many host s...

Communication, Resource sharing and Media (When many host share their resources with every other OR when many devices connect with each other for resource sharing )

Facts about fiber optic cables - Computer Network, Facts about  Fiber Opti...

Facts about  Fiber Optic Cables 1. Outer insulating jacket is made  of Teflon or PVC. 2. Kevler fiber  helps  to strengthen  the cable and prevent breakage. 3. A plas

Why congestion occurs, Q. Why congestion occurs? Congestion Emerg...

Q. Why congestion occurs? Congestion Emerge if the load on the network is greater than the capacity of the network - Load that is the number of packets sent to the net

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