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

Encrypted with a symmetric key, Alice sends a message to Bob, encrypted wit...

Alice sends a message to Bob, encrypted with a symmetric key. Bob decrypts the message and finds it is a purchase order for an expensive workstation. When the time comes to deliver

Give the solutions to the threats, Give the solutions to the threats In...

Give the solutions to the threats In order to implement solutions to the threats, it is advisable that the company should maintain proper password protected hardware. Wherever

System analysis, explain the appropriateness of economic and behavioral fea...

explain the appropriateness of economic and behavioral feasibility

How do we describe the concept of dpu, How do we explain the method of DPU,...

How do we explain the method of DPU, Segments, Datagram, Frame and  packet?

Explain categorization according to pipeline configuration, Categorization ...

Categorization according to pipeline configuration According to the configuration of a pipeline, the below categories are recognized under this classification: Unifunct

How can data to be exchanged between networks, Q. How can data to be exchan...

Q. How can data to be exchanged between Networks? Internetwork Links in an internetwork

What is meant by middleware, Middleware is distributed software required to...

Middleware is distributed software required to support interaction among clients and servers. In short, it is the software that is in the middle of the Client/Server systems and it

Explain parallel computer architecture, Parallel Computer Architecture ...

Parallel Computer Architecture The two key parametric concerns in designing parallel computer architecture are: 1) executing many numbers of instructions concurrently, and

Explain the meaning of negotiation, Explain the meaning of Negotiation ...

Explain the meaning of Negotiation Negotiation is process of getting both sides to agree on some values or parameters to be used during communication. Maximum packet size is on

Explain network services, Explain Network Services Network services are...

Explain Network Services Network services are the thing that a network can do. The main networking services are File Services: This contains file transfer, storage, data m

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