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 meant by 3-tier architecture, In 3-tier Client/Server systems, the ...

In 3-tier Client/Server systems, the application logic (or process) lives in the middle tier and it is removed from the data and the user interface. In theory, the 3-tier Client/Se

Error detection-- crc, Error Detection-- CRC Powerful error detecti...

Error Detection-- CRC Powerful error detection system Rather than addition, binary division is utilized A series of redundant bits called "CRC" or else "CRC remai

Perfect shuffle permutation-concept of permutation network, Perfect Shuffle...

Perfect Shuffle Permutation This was advised by Harold Stone (1971). Consider N objects each characterized by n bit number say  X n-1, X n-2, X 0    (N is chosen such that N

Research, I have a research in this topic " Mitigating DoS Attacks against ...

I have a research in this topic " Mitigating DoS Attacks against Broadcast Authentication in Wireless Sensor Networks " with simulation

Acknowledgment number - transport layer, Acknowledgment number This 32...

Acknowledgment number This 32 bit  field  defines  the byte  number that the  from the  segment is expecting to  receive the segment is expecting to receive from the other par

What are reasons behind using layered protocols, What are reasons behind us...

What are reasons behind using layered protocols  Reasons for using layered protocols, using them leads to breaking up design problem into smaller more manageable pieces and lay

What are the types of transmission media, What are the types of Transmissio...

What are the types of Transmission media? Signals are usually transmitted over some transmission media that are broadly divided in to two categories:- Guided Media: Th

What does jade stands for, QUESTION (a) Briefly describe the dire...

QUESTION (a) Briefly describe the direct coordination model and the meeting oriented coordination model (b) What does JADE stands for? (c) Name the three spec

Define post office and lightweight directory access protocol, Post Office P...

Post Office Protocol and Lightweight Directory Access Protocol POP: Post Office Protocol is a used by mail clients to download messages from a mail server on the Internet. L

What is overlapping signals, Normal 0 false false false ...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4 What is overlapping

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