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 source routing, Q. What is Source Routing? Source Routing ...

Q. What is Source Routing? Source Routing - Sender of packet defines bridges and routes that packet should take - Complete path of bridge IDs and destination address i

Layer on which layer does l2f, Write the layer on which layer does L2F, PPT...

Write the layer on which layer does L2F, PPTP and L2TP operate?

Difference between baseband and broadband transmission, What is difference ...

What is difference between baseband and broadband transmission? In a baseband transmission, the whole bandwidth of the cable is consumed by a one signal. In broadband transmiss

Advantages of firewall, Firewall The NAT router allows receiving of num...

Firewall The NAT router allows receiving of number of a data streams. If it receives a transmission in the form of acknowledgement or data streams or error responses from an ex

Program to load the router with the supplied scripts-ccna, Load the Router ...

Load the Router with the Supplied Scripts Enable ! config term ! hostname Router1 ! enable secret class ! no ip domain-lookup !  interface FastEth

When would we use isdn, We use IDSN supports high speed voice, data and vid...

We use IDSN supports high speed voice, data and video and is a good choice for many small businesses.

What is meant by middleware, Middleware is distributed software required to...

Middleware is distributed software required to support interaction among clients and servers. In short, it is the software that is in the middle of the Client/Server systems and it

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

Explain dynamic key management mechanism, Question: a) Consider the f...

Question: a) Consider the following MIP scenario. Quite a few enterprise networks use private addresses and NAPT for the communication to the Internet. i. Discu

Combinational circuit for sorting the string, Every input line of the combi...

Every input line of the combinational circuit represents an individual element of the string say xi and every output line results in the form of a sorted list. In order to attain t

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