2.1 Bellman-Ford Algorithm and the Distance ...

Bellman-Ford algorithm

	Solves the single-source shortest-path problem in the general case in which edges of a given digraph can have negative weight as long as G (graph) contains no negative cycles.
	The algorithm progressively decreases an estimate d[v] on the weight of the shortest path from the source vertex s to each vertex v in V until it achieve the actual shortest-path.
	The algorithm returns Boolean TRUE if the given digraph contains no negative cycles that are reachable from source vertex s otherwise it returns Boolean FALSE.

Distance vector algorithms

	Use the Bellman-Ford algorithm.
	This approach assigns a number, the cost, to each of the links between each node in the network.
	Nodes will send information from point A to point B via the path that results in the lowest total cost (i.e. the sum of the costs of the links between the nodes used).

2.1 Bellman-Ford Algorithm and the Distance ...

Example of Distance vector algorithm: Routing Information Protocol (RIP )

RIP (Routing Information Protocol) is a widely-used protocol for managing router information within a self-contained network such as a corporate local area network (LAN) or an interconnected group of such LANs.

Using RIP, a gateway host (with a router) sends its entire routing table (which lists all the other hosts it knows about) to its closest neighbor host every 30 seconds. The neighbor host in turn will pass the information on to its next neighbor and so on until all hosts within the network have the same knowledge of routing paths, a state known as network convergence. RIP uses a hop count as a way to determine network distance. (Other protocols use more sophisticated algorithms that include timing as well). Each host with a router in the network uses the routing table information to determine the next host to route a packet to for a specified destination.

2.1 Bellman-Ford Algorithm and the Distance ...