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 are the call routers, What are the Call routers Call routers A, B,...

What are the Call routers Call routers A, B, C, D, and E. There are ten potential lines: AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE. Each of these lines has four possibilities

Show the go-back- N - control variables, Q. Show the Go-back-N - Control Va...

Q. Show the Go-back-N - Control Variables? - S- holds the series number of the recently sent frame - SF - holds sequence number of the first frame in the window - SL - ho

What is OSPF, What is OSPF? It is an Internet routing protocol that scal...

What is OSPF? It is an Internet routing protocol that scales well, can route traffic with multiple paths, and uses knowledge of an Internet's topology to make precise routing de

Explain the architecture and usage of isdn, Computer Networks 1. Write ...

Computer Networks 1. Write about different network structures in use. 2. Explain the architecture and usage of ISDN. 3. Describe the concept of framing in Data Link Layer

Need for standards, Need for standards - Over the past couple of decade...

Need for standards - Over the past couple of decades several of the networks that were built used different hardware and software implementations therefore they were incompatib

Illustrate the products based on socks protocol, Illustrate the products ba...

Illustrate the products based on Socks protocol There are a number of products based on SOCKS specifications such as Auto SOCKS available in the market. The latest version is S

Difference among the communication and transmission, Difference among the c...

Difference among the communication and transmission? Transmission is a physical movement of information and concern issues as bit polarity, synchronization, clock etc. Commu

Multimode for transmitting optical signals, Q. Multimode for transmitting o...

Q. Multimode for transmitting optical signals? - Multiple beams from light source travel through core at different paths - Multimode step-index fiber Density remains

Routing and routed protocols, What is difference among routing and routed p...

What is difference among routing and routed protocols? Ans) i) Routing use for top path selection ii) Routed protocol carries on source and destination information.

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