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

Simple mail transfer protocoland secure sockets layer, Simple Mail Transfer...

Simple Mail Transfer Protocoland Secure Sockets Layer SMTP: Simple Mail Transfer Protocol is a server-to-server protocol for delivering electronic mail. SSL: Secure Sockets

Data sources in circuit-switching mode of operation, A data link is shared ...

A data link is shared by 20 data sources. Each source is active only 10% of the time and produces 1Mbps data rate when active. The sources start their transmissions at random. a

Show coaxial cable connectors, Q. Show Coaxial Cable Connectors? - A mo...

Q. Show Coaxial Cable Connectors? - A most common is barrel connector (BNC) - T-connectors are utilized to branch off to secondary cables - Terminators are necessary for

Function of the transport system and workbench organizer, What is the funct...

What is the function of the transport system and workbench organizer? The function of the transport system and the Workbench Organizer is to handle any changes made to objects

Format of hardware address, FORMAT OF HARDWARE ADDRESS:    It have ...

FORMAT OF HARDWARE ADDRESS:    It have of a numeric value and its size is chosen for specific network technology. The length of the message format is one to six bytes.

Internet address, Addresses are necessary for virtually everything we do on...

Addresses are necessary for virtually everything we do on the Internet. In TCP/IP the IP is a mechanism for providing addresses for computers on the Internet. Internet addresses ha

What do you mean by open system, COMPUTER NETWORKS 1. What do you mean ...

COMPUTER NETWORKS 1. What do you mean by open system? What is the purpose of OSI model? Explain the layered architecture of OSI model. 2. Define the following terms: a) Ana

Packet takes through an internetwork, What utility can you use to see the p...

What utility can you use to see the path a packet takes through an internetwork? Ans) Trace - Uses Time-To-Live (TTL) values to make messages from each router used along the pat

Application to exploring network packet capture, This lab introduces basic ...

This lab introduces basic network capture concepts using Wireshark. Setup You will need a PC running Windows for this lab and you will need to install the Wireshark softwar

Fat tree, Fat tree It is a modified version of the tree network. In thi...

Fat tree It is a modified version of the tree network. In this group the bandwidth of edge (or the connecting wire among nodes) increases towards the root. It is a more practic

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