Computing shortest path in a graph, Computer Networking

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.


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.


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.

Posted Date: 7/31/2012 7:00:00 AM | Location : United States

Related Discussions:- Computing shortest path in a graph, Assignment Help, Ask Question on Computing shortest path in a graph, Get Answer, Expert's Help, Computing shortest path in a graph Discussions

Write discussion on Computing shortest path in a graph
Your posts are moderated
Related Questions
This example demonstrates the use of parallel sections construct. The three functions, fun1, fun2, and fun3, all can be executed concurrently.  Note that all the section directives

Describe the static routing process A static routing method does not adapt to changing conditions on the network but uses a fixed method developed ahead of time. With alternat

Q. Explain Full Duplex data transmission? - Have two separate Communication channels as well as use each one for simplex Data traffic (in different directions). - If this is

can we correct errors using crc?

Source quench is the process where the destination router, or end internetworking device will "quench" the date from the "source", or the source router. This usually occurs when th

WAN interface card(WIC) slots Two fixed WIC slots are present in  2600 series router except 2691. It has contained 3 WIC slots. Network Module Expansion Slot( NM) slot

What is difference between ARP and RARP? The address resolution protocol (ARP) is used to associate the 32 bit IP address with the 48 bit physical address, used by a host or a

Wireless Ethernet (802.11) a) Operates on physical plus data link layers b) BSS (Basic service set) stationary or mobile wireless stations and a central base station known a

Explain the importance of authentication. Authentication is the method of verifying a user's credentials before he can log into the network. It is normally performed using a us