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

Error correction, discuss the concept of redundancy in error detection and ...

discuss the concept of redundancy in error detection and correction

Protocol layering - computer network, Protocol Layering To design  str...

Protocol Layering To design  structural  network protocols the designers organize protocol and use the network  hard ware and software to implement  the protocol  in layers. E

command saves the configuration stored in ram to nvram, Which command save...

Which command saves the configuration stored in RAM to NVRAM Ans) copy running-config startup-config is the command which saves the configuration stored in RAM to NVRAM

Key components of inter-vlan routing , As configuring of VLANs helps in con...

As configuring of VLANs helps in controlling the size of broadcast domains. There are some key components of inter-VLAN routing such as VLAN capable switch Router Ro

Define the class B addresses, Define the Class B Addresses? First t...

Define the Class B Addresses? First two octets are the network number as well as the last two octets are the host number 16382 probable blocks for assignment to organi

What are the ethernet frame fields, Ethernet Frame Fields Preamble ...

Ethernet Frame Fields Preamble - seven bytes of alternating 0s also 1s to notify receiver of incoming frame and to provide synchronization SFD (Start frame delimiter)

Briefly describe about cryptography, Question 1 Describe any five differen...

Question 1 Describe any five different types of computers Question 2 Explain Bus Type LAN. Its advantages and disadvantages and examples Question 3 Explain the s

What are the basic lan topologies, What are the basic LAN topologies? ...

What are the basic LAN topologies? The three simple LAN topologies that are combined to shape any practical topology are called as basic LAN topologies. They are, Bus Topology

Explain ring interconnection networks, Ring: It is a simple linear array w...

Ring: It is a simple linear array where end nodes are associated.  It is equal to a mesh with wrap around connections.  The data transfer in a ring is generally one direction. So,

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