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

What is a management information base, What is a Management Information Bas...

What is a Management Information Base (MIB)? A Management Information Base is part of each SNMP-managed device. Every SNMP agent has the MIB database that having information ab

Prepare the network of spanning tree protocol -ccna, Prepare the Network  ...

Prepare the Network  Step 1: Disable all ports by using the shutdown command. Ensure that the initial switch port states are inactive with the shutdown command. Use the inter

Building distributed systems, Unfortunately, building real-life distributed...

Unfortunately, building real-life distributed systems is not easy. It is hard, for instance, to implement instructions such as "send this data structure to be processed on that com

What is cam, CAM- Content Address Memory.  Its another name of MAC address ...

CAM- Content Address Memory.  Its another name of MAC address table.

Labels and label switching, An ATM network is created from interconnected A...

An ATM network is created from interconnected ATM switches. The attachment ports or points can be connected to computers or other ATM switches. As cells reach at an ATM switch, the

Explain simple mail transfer protocol, Q. Explain Simple Mail Transfer Prot...

Q. Explain Simple Mail Transfer Protocol? Electronic Mail -Simple Mail Transfer Protocol (SMTP) is used to support email on the Internet -Addressing consists of two pa

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)

Discuss the architecture and applications of e-mail, Question 1 Discuss th...

Question 1 Discuss the following Switching Mechanisms- Circuit switching Message switching Packet switching   Question 2 Discuss the following IEEE standard

State the disadvantages of adaptive routing process, State the Disadvantage...

State the Disadvantages of adaptive routing process  (1) The routing decision is more difficult; thus, the processing burden on network nodes enhances. (2) In most cases, ad

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