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.

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.

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
DNS Tunneling – Domain Name Server "If, on one system, it is possible to transmit bits to another in any form, and in turn receive a reply as a result of that transmission, th

QUESTION (a) In CSS, each element in a document is considered to be in an invisible box. Give three ways how to make the box visible (b) (i) Explain the meaning and use of t

How an Ethernet Worked? The operation of Ethernet can be explained in simple terms as follows: Each computer on the Ethernet Network, also called as a node, operates indepen


What is the Network Time Protocol? A protocol that makes sures accurate local timekeeping with reference to radio and atomic clocks located on the Internet. This protocol is c

What is Ring topology The network consists of a set of repeaters joined by point-to-point links in a closed loop. Each station attaches to the network at a repeater and can tra

a)  Which of the well-known Internet applications uses a separate TCP connection for control?   b)  The separate control connection as in (a) above is an example of control (sig

What is a Multiplexor

List the Advantages of microwaves.  a. They need no right of way acquisition among towers. b. They can carry high quantities of information because of their high operating f

In a client's software , the structure of an Internet server's address keyed is as follows: Where: http refer for the communication protocol to be used www refer for th