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

Explain the classification according to level of processing, Classification...

Classification according to level of processing According to this categorization computer operations are classified like arithmetic operations and instruction execution. Subseq

Configure the physical topology- ccna, Configure the Physical Topology ...

Configure the Physical Topology Step 1: Cable the network. Refer to the figure and table below for the essential cables. Step 2: Physically connect lab devices. C

What are the basic lan topologies, What are the basic LAN topologies? ...

What are the basic LAN topologies? The three simple LAN topologies that are combined to shape any practical topology are called as basic LAN topologies. They are, Bus Topology

Database management, today, what is the most common or mostly encountered p...

today, what is the most common or mostly encountered problem in terms of database management system?

Determine the term- cyberspace, Determine the term- Cyberspace The c...

Determine the term- Cyberspace The conceptual or virtual area where pages, data, images, and all the rest are stored. It is the area from where requests are accepted and ful

Describe about the server and browser software, Describe about the Server a...

Describe about the Server and browser software Most of the server and browser software developed by various vendors carry out encryption using either a 40-bit or a 128-bit sec

Describe about the noiseless channel, Describe about the noiseless channel ...

Describe about the noiseless channel A noiseless channel can transmit an arbitrarily large amount of information, no matter how frequently it is sampled. Just send a lot of dat

Characteristics of udp, UDP sends packets 'blind' down the network, and rel...

UDP sends packets 'blind' down the network, and relies on upper-layer protocols to form connections and identify errors. TCP is a connection-oriented protocol that can give reliabl

State briefly about fddi media, FDDI Media Class B or SAS (single-attac...

FDDI Media Class B or SAS (single-attachment stations) attach to one ring Class A or DAS (dual attachment stations) attach to both rings. SASs is attached to the primary rin

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.

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