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

Explain sonet frame transaction, Sonet Frame Transaction Transmitted ...

Sonet Frame Transaction Transmitted one subsequent to another without any gap in between. First 2 bytes - alignment bytes. F628 in Hex. - define the beginning of every

Illustrate unipolar line coding, Q Illustrate Unipolar line coding? - ...

Q Illustrate Unipolar line coding? - Simplest method is inexpensive - Utilizes only one voltage level - Polarity is habitually assigned to binary 1 a 0 is represented by

What are the advantages of adaptive routing, What are the Advantages of ada...

What are the Advantages of adaptive routing  (1) An adaptive routing method can improve performance, as realised by the network user. (2) An adaptive routing method can aid

What is the use of a default gateway, What is the use of a default gateway?...

What is the use of a default gateway? Default gateways give means for the local networks to connect to the external network. The default gateway for connecting to the external

Connection-oriented protocol, TCP is connection-oriented. Connection-orient...

TCP is connection-oriented. Connection-oriented is a kind of connection established between the source & destination machines before any data is sent that means a connection is est

What is ring topology, What is Ring Topology? The physical ring topolog...

What is Ring Topology? The physical ring topology is a circular loop of point-to-point links. Every device connects directly to the ring or indirectly by and interface device o

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

Problem with broadcasting, PROBLEM WITH BROADCASTING: There are some i...

PROBLEM WITH BROADCASTING: There are some issues with the broadcast. For each broadcast frame on the network every computer uses computational sources and places the data into

Openmp in shared memory programming, OpenMP is a compiler directive based s...

OpenMP is a compiler directive based standard developed in the late 1990s jointly by a group of main computer hardware and software vendors. It is portable across a lot of popular

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

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