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

Protocols are used for logical network addressing, Which of the following p...

Which of the following protocols are used for logical network addressing? Ans) Internet Protocol - IP gives routing and a one interface to the upper layers. No upper layer proto

What are the various security measures, What are the various security meas...

What are the various security measures A matter of prime concern to companies is the overheads in the form of huge investment on extra hardware and software. It is quite possi

Processor arrangements-array, Processor Arrangements It is a very frequ...

Processor Arrangements It is a very frequent event in data parallel programming to group a number of processors to perform definite tasks. To reach this goal, HPF gives a direc

Explain in brief about crc, What is CRC The CRC is computed while trans...

What is CRC The CRC is computed while transmission and appended to output stream as soon as last bit goes out onto wire. If the CRC were in header, it will be necessary to make

How to install an anti-virus program, In a network that contains two server...

In a network that contains two servers and twenty workstations, where is the best place to install an Anti-virus program? An anti-virus program must be installed on all servers

Managing and securing the web utility of the router, Managing and Securing ...

Managing and Securing the Web Utility of the Router Step 1: Configure web access. Navigate to the Administration section. Change the router password to cisco. For Web Uti

Define the bulletin board intranet, Define the Bulletin Board Intranet ...

Define the Bulletin Board Intranet This type of Intranet in an organisation extends to everyone the capability to review or update information that would normally be placed

eigrp protocol update route information, How does EIGRP protocol update ro...

How does EIGRP protocol update route information to its neighbors

Layers, what are the layers covered under end to end later connectivity?

what are the layers covered under end to end later connectivity?

What are general middleware, It consists of the communication stacks, distr...

It consists of the communication stacks, distributed directories, authentication services, network time, RPC, Queuing services along with the network OS extensions like the distrib

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