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

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

Subnet/address mask, To use a subnet or classless address, table under rout...

To use a subnet or classless address, table under routers and hosts that have address must keep two pieces of information with every address: the 32-bit address itself and another

Simplicity - transport layer, Simplicity The advantage of this approa...

Simplicity The advantage of this approach is the simplicity  of receiver buffering. The  receiver need not  buffer out of  order packets the sender must maintain the upper an

Commands and responses - application layer, Commands SMTP uses comma...

Commands SMTP uses commands  and response  to transfer  message between a client  and a  server.  Each  commands  or reply  is terminated by a two character ( carriage re

R-sat networks for pstn and stm v-sat network, S t d "B" 9 m C-BAND EARTH...

S t d "B" 9 m C-BAND EARTH STATION (2001)   This  Earth  Station  is  aligned  with  INTEL  SAT  IOR  66°  and  provide domestic connectivity. R-Sat (Regional Satellite) i

What is mesh topology, What is mesh topology Mesh topology is a setup w...

What is mesh topology Mesh topology is a setup wherein every device is linked directly to each other device on the network. Consequently, it needs that each device has at least

Telnet protocols - transport layer, TELNET Protocols The TCP/ IP proto...

TELNET Protocols The TCP/ IP protocol  suite  includes a simple textual  remote terminal protocols called  TELNET  that allow  a user to log into  a computer across an interne

What is cryptography, The science and art of manipulating messages in order...

The science and art of manipulating messages in order to create them secure is known as cryptography..... Two types are:- Symmetric key cryptography and Asymmetric key crypto

Explain the meaning of negotiation, Explain the meaning of Negotiation ...

Explain the meaning of Negotiation Negotiation is process of getting both sides to agree on some values or parameters to be used during communication. Maximum packet size is on

Multimode for transmitting optical signals, Q. Multimode for transmitting o...

Q. Multimode for transmitting optical signals? - Multiple beams from light source travel through core at different paths - Multimode step-index fiber Density remains

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