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

Internet protocols, A communication protocol is an agreement which specifie...

A communication protocol is an agreement which specifies a common language two computers use to exchange messages. For instance, a protocol denotes the exact format and meaning of

Circuit switched and packet-switched mode for sending a file, Two hosts are...

Two hosts are connected by a path made of four links as shown in the figure below. The links are of data rate R = 2 Mbps each. Host A has a file of size F = 1,000,000 bytes to tran

What is frequency borrowing, What is Frequency borrowing In the simples...

What is Frequency borrowing In the simplest case, frequencies are taken from adjacent cells by congested cells. The frequencies can also be assigned to cells dynamically.

Cost involved in inter-processor communication, Cost Involved in Inter-Proc...

Cost Involved in Inter-Processor Communication As the data is assigned to many processors in a parallel computer while implementing a parallel algorithm, the processors might

Hierarchical addressing and routing, The steps of forwarding the packets of...

The steps of forwarding the packets of information is known routing. The information about receivers is saved in routing tables. Note that several entries have same next hop. It is

Thick ethernet wiring, THICK ETHERNET WIRING:  It needs thick coax cab...

THICK ETHERNET WIRING:  It needs thick coax cable. AUI cable joins from NIC to transceiver. AUI cable take digital signal from NIC to transceiver. The transceiver creates anal

What is multimode graded-index fiber, Q. What is Multimode Graded-Index Fib...

Q. What is Multimode Graded-Index Fiber? - Ever since the core density decreases with distance from the centre the light beams refract into a curve - Eliminates problem with

For making assignment, can you make the assignment plagiarism free and when...

can you make the assignment plagiarism free and when you give me back the assignment. Thanks

Internet protocols control protocols ipcp, Internet  Protocols  Control P...

Internet  Protocols  Control Protocols ( IPCP)  The  internet  protocols  control protocols  establishes  configures and terminates the TCP/ IP network  protocols  layer in a PPP

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