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

Direct isp service through leased line, The most expensive method of access...

The most expensive method of accessing the Internet is to employ leased lines that directly connect to the ISP. This will enhance access rate to anywhere between 64 K and 1.5 Mbps,

What is proxy serer and firewall, What is Proxy Sever and Firewall Pro...

What is Proxy Sever and Firewall Proxy Sever Also known as a proxy or application level gateway. It is an application that breaks the connection among sender and receiver.

Data communication and networking, i) Identify at least two items at every ...

i) Identify at least two items at every site that needs upgrading [2 Marks] ii) What type of WAN connection (link) might you use to connect the three sites to each other?

Which type for communication switch do, In case of any new event switch do ...

In case of any new event switch do broadcast, after that always do Unicast.

What is exterior gateway protocol, What is EGP (Exterior Gateway Protocol)?...

What is EGP (Exterior Gateway Protocol)? It is the protocol the routers in neighboring autonomous systems use to recognize the set of networks that can be reached within or by

What do you understand by the term lan, Question: (a) What do you mean...

Question: (a) What do you meant by the term ‘LAN'? How is a LAN different from a WAN? (b) Explain three types of cables which are commonly used with LANs. (c) Three com

Define poison reverse, By entering a 16 as the hop count, the other routers...

By entering a 16 as the hop count, the other routers recognize that the destination is unreachable.

Clos network, Clos network This network was organized by Clos (1953).  ...

Clos network This network was organized by Clos (1953).  It is a non-blocking network and gives full connectivity like crossbar network but it also requires significantly minim

Programming based on message passing, Programming Based on Message Passing ...

Programming Based on Message Passing As we know, the programming model based on message passing uses high level programming languages like C/C++ along with a number of message

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