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

Create a client and a server - message queues & socket, Lab will require yo...

Lab will require you to create a client and a server that communicate over either message queues, sockets, or a well known fifo. The data passed will be a simple request/response i

Data link layer responsibilities, Q. Data Link Layer Responsibilities? ...

Q. Data Link Layer Responsibilities? - Defines frames into manageable data units - Physical addressing - Flow control - Error control - Access control Nod

Describe essential security services, Problem: (a) Application Layer pr...

Problem: (a) Application Layer protocols can be classified as connection-oriented or connectionless-oriented. i. What do you understand by the term protocol? ii. Give an e

Describe about radio waves, Radio Waves - Frequency ranges: 3 KHz to 1...

Radio Waves - Frequency ranges: 3 KHz to 1 GHz - Omni directional - Susceptible to interference by other antennas utilizing same frequency or band - Ideal for long-di

What is quantum computing, In quantum computing, we use the method of qubit...

In quantum computing, we use the method of qubits, superposition and coherence. A normal bit can be in only two states - 0 and 1. But a qubit it can be in 0, 1, or in the superposi

Acknowledgment number - transport layer, Acknowledgment number This 32...

Acknowledgment number This 32 bit  field  defines  the byte  number that the  from the  segment is expecting to  receive the segment is expecting to receive from the other par

Define what is interior and exterior routing protocol, Can you define what ...

Can you define what is interior and exterior routing protocols?

Connectionless multiplexing and de multiplexing, Connectionless Multiplexi...

Connectionless Multiplexing  and De multiplexing Java program running in a host can create a UDP socket  with the  line Datagram's socket my socket =  new datagram's socket

Virtual local area network, VLAN ( Virtual Local Area Network) is a concept...

VLAN ( Virtual Local Area Network) is a concept of creating distinct broadcast domains. It is a network which aims at partitioning the physical network. VLAN comprises all the attr

Computing shortest path in a graph, While calculating shortest path, first ...

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 on

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