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 beaconing, Normal 0 false false false EN-IN X...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

What are the key elements of protocols, What are the key elements of protoc...

What are the key elements of protocols? The key elements of protocols are a. Syntax   It refers to the structure or format of the data that is the order in which they a

Merits of message passage-shared memory, Gives excellent low-level control ...

Gives excellent low-level control of parallelism; Portable; Minimal overhead in data distribution and parallel synchronisation; and It is less error prone. Drawb

Merit and drawback of mpi, Merits of MPI Runs on any shared or dist...

Merits of MPI Runs on any shared or distributed memory architectures; Can be used on a wider range of troubles than OpenMP; Every process has its own local variabl

What is crc and checksum, What is CRC and Checksum CRC (Cyclic redudan...

What is CRC and Checksum CRC (Cyclic redudancy check) CRC, is the most powerful of the redundancy checking methods, is based on binary division. Checksum Checksum

Latency and scalability, Latency : In interconnection networks a variety of...

Latency : In interconnection networks a variety of nodes may be at dissimilar distances depending upon the topology. The network latency differs to the worst-case time wait for a u

Efficiency vs. number of processors, Efficiency :- The other main metr...

Efficiency :- The other main metric used for performance measurement is efficiency of parallel computer system i.e. how the resources of the parallel systems are being utilized

Transport protocols - udp and tcp, Most real-life applications are built on...

Most real-life applications are built on top of the UDP and TCP transport protocols. UDP, which stands for User Datagram Protocol, provides the capability of delivering individual

Define routing, Define Routing? The process of determining systematical...

Define Routing? The process of determining systematically hoe to forward messages toward the destination nodes based on its address is known as routing.

Which statement best defines access list placement, When using access lists...

When using access lists, it is important where those access lists are placed. Which Statement best defines access list placement Ans) Put standard access lists as near the desti

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