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

What is beaconing, What is Beaconing? The process that permits a networ...

What is Beaconing? The process that permits a network to self-repair networks problems. The stations on the network notify the other stations on the ring when they are not rece

Labels and label switching, An ATM network is created from interconnected A...

An ATM network is created from interconnected ATM switches. The attachment ports or points can be connected to computers or other ATM switches. As cells reach at an ATM switch, the

A default route is analogous to a, A default route is analogous to a defaul...

A default route is analogous to a default gateway. It is used to decrease the length of routing tables and to give complete routing capabilities when a router may not know the rout

Flash updates, IGRP uses flash updates, poison reverse updates, hold down t...

IGRP uses flash updates, poison reverse updates, hold down times, and divide horizon. How often does it broadcast its routing table updates? Ans) 90 seconds

Memory pools-input and output pool-pci pool, Memory Pools IOS manages a...

Memory Pools IOS manages available free memory thorugh  memory pool series, which are essentially heaps in the generic sense; each pool is a set of memory blocks that can be al

Physical media - computer network, Physical Media In order  to define ...

Physical Media In order  to define what is meant by a physical medium let us reflect on the brief life of a bit. Consider  a bit travelling from one end system through a serie

Computer Networking help, Hello, I have a question which is due tomorrow (2...

Hello, I have a question which is due tomorrow (2/15/2013) at 11:55pm. The configuration portion of the exercise has been completed. I only need the questions in bold answered (onl

Http request message, HTTP Request Message The first  line of  an HTTP...

HTTP Request Message The first  line of  an HTTP request message  is called the  line. The subsequent lines are called  the header lines. The  request  line has  fields the me

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

Determine the computing infrastructure, Determine the computing infrastruct...

Determine the computing infrastructure One solution for the protection of the computing infrastructure is to use digital certificate-based solutions. Users can be given access

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