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

Communication protocol - internet protocol, The Internet protocol mentions ...

The Internet protocol mentions the rules that describe the details of how computers communicate. It exactly mentions how a packet should be formed & how a router should forward eac

What is redirector in networking, What is redirector in Networking? Red...

What is redirector in Networking? Redirector is software that intercepts file or prints I/O requests and changes them into network requests. This comes under presentation layer

Connectionless service, In connectionless schema, there is no connection re...

In connectionless schema, there is no connection required. The source of data includes destination information in data and transmit to the network. Network transmit each data item

Write the concept of simplex, Describe Concept of Simplex, Half Duplex and ...

Describe Concept of Simplex, Half Duplex and Full Duplex dialogs?

network consultant, Network Consultant, My name is Jason Long. I am th...

Network Consultant, My name is Jason Long. I am the CEO of IL Corporation. IL is an investment firm that performs financial services to many organizations. We currently have a

Determine about the complete and proper security, Determine about the Compl...

Determine about the Complete and proper security Complete and proper security configuration and administration is indeed a complex issue. One should think carefully about the

Selective repeat (sr) - transport layer, Selective Repeat (SR) Select...

Selective Repeat (SR) Selective repeats is a connection oriented protocols  in which  transmitter and receiver have a window  of sequence numbers. SR scheme  avoids  the  unne

Determine how many bits are used for the page number, 1.  A virtual memory ...

1.  A virtual memory system has a virtual address space of 4 Gigabytes and a page size of 8 Kilobytes.  Each page table entry occupies 4 bytes.   a)  How many bits remain unchanged

Command that shows traffic statistics on serial 0/1, Recognize the command ...

Recognize the command that shows traffic statistics on serial0/1? Ans) show interface serial 0/1

FTP, study on FTP

study on FTP

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