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

Whcih is the routing metric used by rip, Routing Information Protocol (RIP)...

Routing Information Protocol (RIP) is a distance vector routing protocol that used hop count as its metric. The maximum hop count is 15, 16 hops are considered unreachable. RIP upd

In formation sharing at regular intervals, In formation  sharing at  regu...

In formation  sharing at  regular intervals For example  every 30 seconds each router sends its information  about the  whole  network  to its  neighbours. This sharing  occurs

Define retransmission, Define Retransmission? Retransmission is a proce...

Define Retransmission? Retransmission is a process in which the receiver detects the occurrence of an error and asks the sender to resend the message. Resending is repeated unt

What is the protocol number for udp, User Datagram Protocol - UDP is a conn...

User Datagram Protocol - UDP is a connectionless oriented transport protocol for use when the upper layers give error-recovery and reliability. UDP does not series data or re-assem

What are the value added services, What are the value added services Ma...

What are the value added services Many organisations are demanding higher services (also called value added services) such as faxing, minimal cost call routing, connectivity to

Briefly describe nat and rip, Briefly describe NAT and RIP NAT is Netwo...

Briefly describe NAT and RIP NAT is Network Address Translation. This is a protocol that gives a way for multiple computers on a common network to share one connection to the I

Network virtual terminal - transport layer , Normal 0 false f...

Normal 0 false false false EN-IN X-NONE X-NONE

url connection instance, What is the difference among URL instance and URL...

What is the difference among URL instance and URL Connection instance? Ans) A URL instance represents the location of a resource, and a URL Connection instance shows a link for

Parallel programming environment characteristics, Parallel Programming Envi...

Parallel Programming Environment Characteristics  The parallel programming environment consists of an debugger, a editor,  performance evaluator and programme visualizer for i

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