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 is sockets, A socket is an abstraction that shows an endpoint of commu...

A socket is an abstraction that shows an endpoint of communication. Most applications that consciously use TCP and UDP do so by making a socket of the appropriate type and then per

What is one basic requirement for establishing vlan, What is one basic requ...

What is one basic requirement for establishing VLANs? A VLAN needs dedicated equipment on each end of the connection that permits messages entering the Internet to be encrypted

Describe one security measure against reverse tunneling, Question: a) I...

Question: a) In route-optimized communication, a mobile node sends packets to a correspondent using the home address present in the destination option. Why does the design use

Different kinds of firewall architectures, What are the different kinds of ...

What are the different kinds of firewall architectures?

Developing prototypes - digital receipts, Increasingly it is the quality of...

Increasingly it is the quality of the interface of mobile phones that are giving competitors the edge.  Users not only make selections based on cost but also functionality and cert

Classes and dotted decimal notation, The relationship between dotted decima...

The relationship between dotted decimal notation and classes is shown as follows. In class A the three octets managed to a host suffix. In class B the last most two octets ar

What are the control frames for lost tokens, Control Frames for Lost Tokens...

Control Frames for Lost Tokens If station goes down ... token lost Predecessor listens for data frame or token Noticing none, retransmits token Sends whofoll

Explain about traffic shaping, Q. Explain about Traffic shaping ? Traf...

Q. Explain about Traffic shaping ? Traffic shaping -Method to control the amount and the rate of the traffic sent to the network.? Leaky bucket Token bucket -

Networking, Discuss the interdependence of networking hardware and software...

Discuss the interdependence of networking hardware and software. Is it possible to have one without the other?

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