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

List all application layer and transport layer protocols, a)  A host is sen...

a)  A host is sending a HTTP request to a HTTP server. In the table below, propose a correct set of source and destination port numbers for segments sent from host to server and fr

Modern computer , modern technology in world of 21 century

modern technology in world of 21 century

What are the drawbacks of wireless devices, What are the drawbacks of wirel...

What are the drawbacks of wireless devices One drawback is security. Every random delivery man who happens to be in building can listen on network. Another weakness is reliabil

Cisco express forwarding and interface controllers , Cisco Express Forwardi...

Cisco Express Forwarding CEF is a new method of switching that available in IOS, its overcome the drawbacks of fast switching method In IOS packet switching, There are thre

Network topologies- -fundamentals of networks, Network Topologies Topo...

Network Topologies Topology is study  of the  arrangement or  mapping of  the elements links nodes etc,  of a network especially the physical and logical inter connections bet

Ipx traffic on a network, To monitor ipx traffic on a network, what command...

To monitor ipx traffic on a network, what command would we use? Ans) show ipx traffic

Describe the following topics, Describe the following topics A . LAN B . M...

Describe the following topics A . LAN B . MAN C . WAN D . ARPANET

State ethernet frame format, Ethernet Frame Format Consists of sev...

Ethernet Frame Format Consists of seven fields There is No mechanism for acknowledging received frames considered an unreliable medium

Cost saving - application layer, Cost Saving Better performance  scala...

Cost Saving Better performance  scalability  and viability  translates into  saving  for  website  operators.  Because  fewer  application  web servers are required  to meet

Layer responsible for putting 1s and 0s into a logical group, Name the laye...

Name the layer responsible for putting 1s and 0s into a logical group? Ans) Frames are broken down into 1s and 0s and placed onto the physical medium by the Data Lin layer.

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