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

Select a range of addresses, ACME Corp is located in Toledo, Ohio. They wou...

ACME Corp is located in Toledo, Ohio. They would like to create a network and divide it into 3 subnets, each subnet has 150 computers. The IT plan calls for connecting the LAN to t

Layers, what are the layers covered under end to end later connectivity?

what are the layers covered under end to end later connectivity?

Tcp, how tcp is redefined for wireless network

how tcp is redefined for wireless network

Half duplex ethernet operation, Half-Duplex - Capability for data transmis...

Half-Duplex - Capability for data transmission in only single direction at a time among sending station and a receiving station.

Advantages and disadvantages of client-server method, 1. Write a critical a...

1. Write a critical analysis of the client/server vs. service architecture method for developing service architectures.  You must explain what the client/server method is in terms

Determine how many bits are used for the page number, 1.  A virtual memory ...

1.  A virtual memory system has a virtual address space of 4 Gigabytes and a page size of 8 Kilobytes.  Each page table entry occupies 4 bytes.   a)  How many bits remain unchanged

Internet transport service proposal, will you have this done to day? And ho...

will you have this done to day? And how long will this take?

Enable wireless security - ccna, Enable Wireless Security Step : Confi...

Enable Wireless Security Step : Configure Windows to use WEP authentication.  Navigate to the Network Connections page again and right-click the Wireless Network Connection

Determine the level of fibre channel standard, Determine the level of Fibre...

Determine the level of Fibre Channel standard The Fibre Channel standard is organized into five levels: FC-0: The Physical Interface and Media Level handles a variety of phy

What is the difference between a hub and a switch, What is the difference b...

What is the difference between a hub and a switch? A hub acts as a multiport repeater. Though, as more and more devices connect to it, it would not be able to efficiently manag

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