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 ip address representation, Q. Show the IP Address Representation? ...

Q. Show the IP Address Representation? IP Addressing IP Address Representation Binary notation - IP address is displayed as 32 bits Dotted-decimal notation -

What are diagrams and trigrams, What are Diagrams and Trigrams? The mos...

What are Diagrams and Trigrams? The most ordinary two letter combinations are known as diagrams. e.g. th, in, er, re and an. The most common three letter combinations are known

Data sources in circuit-switching mode of operation, A data link is shared ...

A data link is shared by 20 data sources. Each source is active only 10% of the time and produces 1Mbps data rate when active. The sources start their transmissions at random. a

Describe the dsdm life-cycle with a suitable diagram, Question : (a) De...

Question : (a) Describe how ‘prototyping' is important to RAD. (b) List main features of ‘prototyping'. (c) List main principles of DSDM. (d) Describe the DSDM life-

osi layer performs code conversion, Name the OSI layer which performs code...

Name the OSI layer which performs code conversion, code formatting and encryption Ans) Presentation layer performs code conversion, code formatting and encryption

Explain the term hardware cost, Hardware Cost It indicates to the cost ...

Hardware Cost It indicates to the cost concerned in the functioning of an interconnection network. It comprises the cost of arbiter unit, connectors, switches, interface logic

Explain about wireless ethernet, Wireless Ethernet (802.11) a) Operates...

Wireless Ethernet (802.11) a) Operates on physical plus data link layers b) BSS (Basic service set) stationary or mobile wireless stations and a central base station known a

What security risks present on the networks, Security risks present on the ...

Security risks present on the networks Lots of risks are present everywhere on Internet as well as on Intranet, if it is not known what is being done. Every day a number of

Difference between authentication and deauthentication, Difference between ...

Difference between Authentication and Deauthentication Authentication: Used to establish the self of stations to each other. Deauthentication: This service is appealed whene

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