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 layer can optionally support reliability, Ans) The Transport Layer : ...

Ans) The Transport Layer : Segments upper-layer applications. Establishes an end-to-end connection. Sends segments from one end host to another. Optionally, make sures

What is network architecture, What is Network Architecture? When two o...

What is Network Architecture? When two or more computer are linked with one another for the purpose of communicating data electronically, besides physical connection of comput

Network topology, identify different network topologies.

identify different network topologies.

netware protocol works on layer 3, Which NetWare protocol works on layer 3...

Which NetWare protocol works on layer 3--network layer-of the OSI model? Ans)IPX

Operating system - server and client, Operating System - Server and Client ...

Operating System - Server and Client Various operating systems that support Intranets are all variants of Windows and Unix. In addition to these, certain other software releva

What are the threats include in computer software, What are the threats inc...

What are the threats include in computer software The second component vulnerable to threats to the system is software. Threats to software may include, but are not limited to

Determine 10base-fl- fiber link ethernet, 10Base-FL: Fiber Link Ethernet ...

10Base-FL: Fiber Link Ethernet Utilizes star topology to connect stations to a hub External transceiver entitle as a fiber-optic MAU connects processing device to fib

Explain about bandwidth – delay product, Q. Explain about Bandwidth – delay...

Q. Explain about Bandwidth – delay product? Bandwidth - delay product - A measure of competence of ARQ system = bandwidth (bits per second) * round-trip delay (in seco

What is a pseudo TTY, What is a pseudo tty? A pseudo tty or false termi...

What is a pseudo tty? A pseudo tty or false terminal enables external machines to connect by Telnet or rlogin. Without a pseudo tty, no connection can take place.

Maintaining the sequence number, Maintaining the sequence number The  ...

Maintaining the sequence number The  other advantage of GBN  is that  it maintain  the next  sequence number.

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