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

Challenge handshake authentication protocols (chap), Challenge Handshake Au...

Challenge Handshake Authentication Protocols (CHAP) CHAP as its an implies implements  a form of authentication that  requires a challenge  and a response. A CHAP authenticator

What is the full form of FDM and TDM, What is the full form of FDM and TDM ...

What is the full form of FDM and TDM It is both. Each of the 100 channels is possess its own frequency band (FDM), and on every channel two logical streams are intermixed by th

Packets in eigrp, What are different kinds of packets in EIGRP?

What are different kinds of packets in EIGRP?

Initialization - network layer and routing , Initialization  Imagine t...

Initialization  Imagine that  all routers in our  sample internetwork  comes up  at the  same time. Each router sends a greeting packet to its  neighbours to find  out the  sta

Hyper text transfer protocols ( http), Hyper  Text Transfer Protocols ( HT...

Hyper  Text Transfer Protocols ( HTTP) The Hyper text  protocols ( HTTP) is at  the heart  of the  web. If a browser  developer follows  the rules  of the HTTP, the  browser w

Explain how tcp handles connection-setup management, Problem: (a) Expla...

Problem: (a) Explain how TCP handles connection-setup management. (b) Each host on the Internet is currently assigned an IP address 32 bits long (IPv4). IPv4 addresses are u

How do you disable cdp on the whole router, By using this command Router(c...

By using this command Router(config)# no cdp run we can disable CDP on the entire Router

Explain the terms - lan extension and ad hoc network, Explain the terms - L...

Explain the terms - LAN extension and Ad hoc network LAN extension: a wireless LAN integrated with a wired LAN to extend the coverage area of the LAN complex; Cross-building

LAN, what is man LAN wan

what is man LAN wan

Straight through lan cable, Q. Straight through Lan Cable ? Straight t...

Q. Straight through Lan Cable ? Straight through Cable - Maintain the pin connection each the way through the cable. - The wire connected to pin 1 is the similar on bo

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