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

Explain the uses of firewall in computer, Explain the uses of Firewall in c...

Explain the uses of Firewall in computer For Intranet developers, restricting access of unauthorised users to the Web site has been the greatest challenge. In addition to preve

Relevance and protection regarding dns attacks, Relevance and Protection re...

Relevance and Protection regarding DNS Attacks While discussing about the relevance and protection of the database, there are many things which need to consider. Almost, may o

Describe the hardware complexity of benz network, Q. Describe the Hardware ...

Q. Describe the Hardware complexity of Benz Network? Hardware complexity of Benz Network:  Benz network employs lesser switches and it gives good connectivity. To come across h

Command to configure a explanation on an interface, Recognize the command t...

Recognize the command to configure a explanation on an interface Ans) Router(config-if)# explanation Finance department

Benefits of mpls vpn- wireless technology, 1) The school has implemented a ...

1) The school has implemented a pilot MPLS VPN which is being evaluated to replace the Bell South Frame Relay solution that provides connectivity to the Bascom Palmer Eye-Institute

Comp architecture, In reg-mem architecture, clock cycle is 10 ns wide. It i...

In reg-mem architecture, clock cycle is 10 ns wide. It is proposed that reg-reg architecture be used instead, that reduces the clock cycle by 2 ns. However, it requires an addition

Output port - network layer and routing , Output Port The function of t...

Output Port The function of the  port is  take  the packets that have  been stored in the out  put port  memory and transmits them over the out going  link. The queuing  and bu

LTE, What is LTE ?

What is LTE ?

Thin ethernet wiring, THIN ETHERNET WIRING: Thin Ethernet needs thin c...

THIN ETHERNET WIRING: Thin Ethernet needs thin coax cable that is cost effective and easier to install than thick Ethernet coax. In this case transceiver electronics are creat

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