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

The world wide web http, The World  Wide Web HTTP The Hyper text Tran...

The World  Wide Web HTTP The Hyper text Transfer Protocols( HTTP) is a protocols  used mainly to  access data on the world  wide  web. HTTP functions as a carbonation of FTP(

Concept of permutation network, Concept Of Permutation Network In permu...

Concept Of Permutation Network In permutation interconnection networks the information replace requires data transfer from input set of nodes to output set of nodes and likely

Roles of host system, Q.Role of Host System? Hosts on OSI implementatio...

Q.Role of Host System? Hosts on OSI implementations don't handle network operations (simple terminal) but TCP/IP hosts participate in most network protocols. TCP/IP hosts do su

A Comparative Study between MPLS VPN and the Public Internet, A Comparative...

A Comparative Study between MPLS VPN and the Public Internet which has intro. operation of tecnology, analysis, discussion, recommendation, conclusion.

Single mode for transmitting optical signals, Q. Single Mode for transmitti...

Q. Single Mode for transmitting optical signals? - Merely one beam from a light source is transmitted using a smaller range of angles - Smaller diameter as well as lower de

Show vpns security and the internet model, Q. Show VPNs Security and the In...

Q. Show VPNs Security and the Internet Model? - VPN's Security and the Internet Model - Application layer - provide for each application protocol (other layers may be left v

State the characteristics of thinnet, Thinnet Characteristics Short...

Thinnet Characteristics Shorter range (185 meters) as well as smaller capacity Bus topology LAN Connectors and cables include: thin coaxial cable, NICs and BNC-T

Transmission robustness and security, Transmission robustness and security ...

Transmission robustness and security Unless properly designed, a wireless LAN might be interference prone and simply eavesdropped. The design of a wireless LAN must allow relia

What is a tp monitor, What is a TP Monitor? There is no commonly accept...

What is a TP Monitor? There is no commonly accepted explanation for a TP monitor. According to Jeri Edwards' a TP Monitor is "an OS for transaction processing".

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