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 are hold-downs used for, Hold-Down Timers - Routers ignore network upd...

Hold-Down Timers - Routers ignore network update information for a number of periods.

Message passing libraries mpi and pvm, In this part, we shall talk about ab...

In this part, we shall talk about about message passing libraries. In history, various message passing libraries have been available since the 1980s. These executions differed subs

Explain collision, When the signal hits to each other, collision accord.

When the signal hits to each other, collision accord.

What are the access methods used in lan, What are the Access methods used i...

What are the Access methods used in LAN: i. Switched access: It is used in LANs which are assigned around CBXs. Electronic switching is techniques are used to provide access

What is client/server, What is client/server? Client/server is a type o...

What is client/server? Client/server is a type of network wherein one or more computers act as servers. Servers give a centralized repository of resources like printers and fil

Distinguish between flow control and congestion control, Question: (a) ...

Question: (a) Distinguish between Flow Control and Congestion Control. (b) Explain clearly how a URL is resolved by a computer. (c) List one application that uses TCP

Debug ip igrp transaction, To monitor IP igrp traffic, we can use "debug IP...

To monitor IP igrp traffic, we can use "debug IP igrp transaction" or "debug IP igrp events". How do we show information about IPX routing update packets? Ans) Bu using debug ip

Explain simple mail transfer protocol, Q. Explain Simple Mail Transfer Prot...

Q. Explain Simple Mail Transfer Protocol? Electronic Mail -Simple Mail Transfer Protocol (SMTP) is used to support email on the Internet -Addressing consists of two pa

Why you require connecting two computers for file sharing, You require conn...

You require connecting two computers for file sharing. Is it possible to do this without using a hub or router? Yes, you can connect two computers together using only one cable

Gateway - networl layer and routing , Gateway A gateway  is an internet...

Gateway A gateway  is an internetwork  device which  joins different  network  protocols  together. It woods on all  seven  layers of OSI model. Gateways are also known as  pro

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