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

Networking & computer architecture long question, Write discussion on Assoc...

Write discussion on Associative mapping - computer architecture.

Describe the tcp/ip reference model, Computer Networks 1. Differentiate...

Computer Networks 1. Differentiate WAN and LAN. 2. Describe the TCP/IP Reference Model with diagram. 3. Explain Circuit switching and message switching. 4. List the fu

State about the bus topology, State about the Bus Topology Comments ...

State about the Bus Topology Comments 1 - Requires less cabling than a star network 2 - If there is a central cable problem entire netwo. rk goes down 3 - Less e

Reliable data transfer - transport layer, Reliable Data Transfer Figur...

Reliable Data Transfer Figure illustrate the  framework for reliable  transfer. The service  abstraction provided  to the upper  layer  entities is that  of a reliable channel

Simple Pendulum, Give me a wide idea about simple pendulum and its types wi...

Give me a wide idea about simple pendulum and its types with equation and tables as usual assignment?

Determine about the tcp/ip, Determine about the TCP/IP Stands for Tr...

Determine about the TCP/IP Stands for Transmission Control Protocol/Internet Protocol. This is the group of protocols that define the Internet and communication method used

Enumerate about the virtual private network, Enumerate about the Virtual Pr...

Enumerate about the Virtual Private Network (VPN) Even though, many firewalls also include the features of the virtual private network, the functionality and capabilities of V

Explain asynchronous FDDI, Explain Asynchronous FDDI Asynchronous bandw...

Explain Asynchronous FDDI Asynchronous bandwidth is allocated utilizing an eight-level priority scheme. Every station is assigned an asynchronous priority level. FDDI as wel

Network topology, identify different network topologies.

identify different network topologies.

Key features of spontaneous networking, QUESTION a) Give a detailed exp...

QUESTION a) Give a detailed explanation of the following: Some dynamics systems can be built as variations on the client server model. b) Give one main drawback of the "Thin

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