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

IP address, what is variable ip address

what is variable ip address

Configure spanning tree- ccna, Configure Spanning Tree Step 1: Ex...

Configure Spanning Tree Step 1: Examine the default configuration of 802.1D STP. On each switch, display the spanning tree table with the show spanning-tree command. R

What is cross over cable, Q. What is Cross over cable? - Cross the crit...

Q. What is Cross over cable? - Cross the critical pair to properly transmit, align and receive signals on devices with like connections. - Pin 1 connected to pin 3 as well a

What is tcp/ip, What is TCP/IP TCP/IP is short for Transmission Control...

What is TCP/IP TCP/IP is short for Transmission Control Protocol / Internet Protocol. This is a set of protocol layers that is intended to make data exchange possible on dissim

D2D communication, I need to discuss with some one who expert in D2D commun...

I need to discuss with some one who expert in D2D communications in 5G networks.

What is tdm, What is TDM? TDM is a digital process that can be applied ...

What is TDM? TDM is a digital process that can be applied when the data rate capacity of the transmission medium is greater than the data rate needed by the sending and receivi

Comparison of distance-vector and link-state algorithm, DISTANCE-VECTOR ROU...

DISTANCE-VECTOR ROUTING: It is easy to implement. Packet switch modifies its own routing table first. It is used in RIP. LINK-STATE ALGORITHM: It is ve

Hybrid networks -v irtual private networks , Hybrid Networks Allows  a...

Hybrid Networks Allows  an organization to have its  own  private networks  and at the same  time access to the global internet. the organization  may share  its information w

What are the functions of the typical server program, What are the function...

What are the functions of the typical server program? It waits for client-initiated requests. Executes many requests at the same time. Takes care of VIP clients first. Initiate

Compute the hash - part of the packet, In this question, we study Nested ES...

In this question, we study Nested ESP in AH, that is, we combine ESP with AH. Let's look at the site-to-site VPN scenario shown again in Figure 1. Let's assume that Alice's desktop

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