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 protocol support tools, What are the Protocol Support Tools ...

What are the Protocol Support Tools The Intranet should support the tools meant for providing various services on the Internet through the protocols. In addition to the convent

Design a logical lan topology- ccna, Design a Logical LAN Topology Step...

Design a Logical LAN Topology Step: Design an IP addressing scheme. Given the IP address block of 192.168.7.0 /24, design an IP addressing scheme that states the following r

What is stop-and-wait automatic repeat request, What is Stop-and-Wait Autom...

What is Stop-and-Wait Automatic Repeat Request? Error correction in Stop-and-Wait ARQ is implemented by keeping a copy of the sent frame and retransmitting of the frame when th

What are general middleware, What are General Middleware? It contains t...

What are General Middleware? It contains the communication stacks, authentication services, distributed directories, network time, RPC, Queuing services with the network OS ext

What is a file server, File servers are useful for sharing files through a ...

File servers are useful for sharing files through a network. With a file server, the client passes requests for file records over network to file server

Internet service provider (isp), Internet  Service Provider (ISP) Thi...

Internet  Service Provider (ISP) This  supper fast  network  spanning  the world  from  one major  metropolitan area to another  is provided  by a handful of national internet

Explain concept of permutation network, Concept Of Permutation Network ...

Concept Of Permutation Network In permutation interconnection networks the information transfer necessitates data transfer from input set of nodes to output set of nodes and po

Case study, Scenario: Your Case Study must be based on the information prov...

Scenario: Your Case Study must be based on the information provided. There will be no additional information. This must be submitted in a .doc, or .pdf format. If you send a few

What is aspects of security, Q. What is Aspects of Security? - Securit...

Q. What is Aspects of Security? - Security Attack: Any action whichcompromises the security of information owned by an organization. - Security Mechanism: A mechanism th

Connection-oriented service, Sender requests connection from network. Other...

Sender requests connection from network. Other receiver agrees to connection. Computers interchange data through connection. One-endpoint requests network to split connection when

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