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 how reducing ineffective taxation, Question: (a) With mobile t...

Question: (a) With mobile telecommunications providing an important engine for growth, continuing to stimulate growth and to ensure mobiles remain affordable for all, will re

No retransmission - transport layer, No Retransmission This  protocols...

No Retransmission This  protocols  will not  through  the correctly received packets  but buffers than  and send  acknowledgment  for those packets. Thus  retransmission of th

Communication protocol - internet protocol, The Internet protocol mentions ...

The Internet protocol mentions the rules that describe the details of how computers communicate. It exactly mentions how a packet should be formed & how a router should forward eac

What is unbound transmission media, Unbound Transmission Media Unbound ...

Unbound Transmission Media Unbound transmission media extend beyond the limiting confines of cabling. They give a good communication alternative for WANS. The lack of physical

Applications of fiber optics, Applications of Fiber Optics - Backbone ...

Applications of Fiber Optics - Backbone networks because of wide bandwidth and cost effectiveness - Cable TV - LANS - 100Base-FX (Fast Ethernet)

Describe the concept of successor and feasible successor, Describe the conc...

Describe the concept of successor and feasible successor?

Long term evolution and network requirements-ethernet , You are a network c...

You are a network consultant working for a large European networVservice provider and have been given the task of reviewing the future network requirements of the company for its f

What is meant by symmentric multiprocessing, What is meant by Symmentric Mu...

What is meant by Symmentric Multiprocessing (SMP)? It treats all processors as equal. Any processor can do the work of any other processor. Applications are divided into thread

State 802.11 DSSS , 802.11 DSSS a) Direct sequence spread spectrum in a...

802.11 DSSS a) Direct sequence spread spectrum in a 2.4 GHz band b) Each bit is replaced by a sequence of bits called a chip code, implemented at the physical layer c) Se

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