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

State the example of security audit as case study, State the Example of sec...

State the Example of security audit as case study Linda narrates one of her experience about a security audit. She was performing a spot audit where she was checking certain

What are the major technologies to create client application, What are the ...

What are the five major technologies that can be used to create Client/Server applications? Database Servers Groupware TP Monitors Distributed Objects Intranets.

Show the communication between switches in VLAN, Q. Show the Communication ...

Q. Show the Communication between Switches? Communication between Switches - Must know which station belongs to which VLAN as well as membership of stations connected to

Illustrate the products based on socks protocol, Illustrate the products ba...

Illustrate the products based on Socks protocol There are a number of products based on SOCKS specifications such as Auto SOCKS available in the market. The latest version is S

Name the presentation layer standards, A.) JPEG and PICT B.) MPEG and MI...

A.) JPEG and PICT B.) MPEG and MIDI C.) ASCII and EBCDIC For example, the Presentation layer would be liable for changing from EDCDIC to ASCII. Data compression, decompres

Show upper layers of tcp-ip model, Q. Show Upper Layers of tcp-ip model? ...

Q. Show Upper Layers of tcp-ip model? The Session Layer - The Session layer allows two parties to hold ongoing communications called a session across a network. - Not

Types of Networking, How can I identify the difference types of networks

How can I identify the difference types of networks

What is the use of a default gateway, What is the use of a default gateway?...

What is the use of a default gateway? Default gateways give means for the local networks to connect to the external network. The default gateway for connecting to the external

Topologies, discuss communication isolation and privatization in network to...

discuss communication isolation and privatization in network topologies

What is man, What is MAN? MAN - Metropolitan Area Networks. MAN is b...

What is MAN? MAN - Metropolitan Area Networks. MAN is bigger than a LAN and as its name implies, covers the area of a single city. MANs rarely extend beyond 100 KM and frequ

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