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

Show the error correction by hamming code, Q. Show the Error Correction by ...

Q. Show the Error Correction by Hamming Code? Hamming Code is able to be applied to data units of any length and uses the relationship between data and redundancy bits For i

Difference between trigger and rule, What is the difference between trigger...

What is the difference between trigger and rule? Ans) The triggers are known as implicitly by database generated events, whereas stored procedures are known as explicitly by cli

What are 10base2, 10Base2 an Ethernet term meaning a maximum transmitting r...

10Base2 an Ethernet term meaning a maximum transmitting rate of 10 Megabits per second that uses baseband signaling, with a contiguous cable segment length of 200 meters (185mts).

link layer - computer network, Link Layer To move  to packet  from o...

Link Layer To move  to packet  from one node( host  or packet swtich0 to  net node  in the  route the network  layer  relies  on the  services  of the link layer. Particularl

Difference among the communication and transmission, Difference among the c...

Difference among the communication and transmission. Transmission is a physical movement of information and concern issues like bit polarity, synchronisation, clock etc. Com

Networking project for 20 computers, can i get a sample networking project ...

can i get a sample networking project for 20 computer with all network components?

Type of failures and bathtub curve, AILURES AND BATHTUB CURVE The life ...

AILURES AND BATHTUB CURVE The life of a component system can be grouped into three different phases typical curve depicting these three is called the bathtub curve due to its s

Describe in detail with example how data fragmentation works, Describe in d...

Describe in detail with example how data fragmentation works?

Explain the cost of a path between two nodes, Explain the cost of a path be...

Explain the cost of a path between two nodes Given a network of nodes linked by bidirectional links, where every link has a cost associated with it in each direction, explain t

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