Shortest Path Algorithm: Bellman-ford V.S. Dijkstra's

Dijkstra's: Given a vertex(node), it can find the shortest cost between vertex and very other vertex in the graph.

1. dist[start] =0 and dist[i] = infinity for other vertices i

2. nhop[start] = start and  nhop[i] = -1 for any vertex i (nhop: next hop from start)

3. empty set = {} store marked router

4. while not all routers have been marked

       1). let u be the vertex is unmarked and has smallest dist[u], and mark u

            // In the beginning, start will be marked because dist[start] is 0

            // how to get the smallest dist[u] is not easy: u canot be in the marked set, and u has to be the smallest. skip all the node is marked, then choose the vertex with smallest distance from start to this vertex

       2). for all neighbors v of u, dist[v] = min{dist[v], dist[u]+cost[u,v]}

       3). if dist[v] > (dist[u]+cost[u,v]), 

            nhop[v] = v (u=start) or nhop[u] otherwise

Run time of this algo. O(V^2), if you use heap to store the dist[i], run time O(E+VlogV)

Bellman-ford: the basic idea is very similar to Dijkstra's, but instead of selecting the shortest distance neighbour edges, it select all the neighbour edges.

Run time of this algo. O(|V|*|E|)

Routing Protocol Example:
Bellman-ford: distance vector routing(RIP)
Dijkstra's: link state routing(OSPF)

more info:
wiki dijkstra's bellman-ford