Shortest path Algorithm

Given a graph, the source and the destination, it is an important problem to find the shortest path between the source and the destination. Shortest path is used in scheduling, routing and other application areas.
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.

# Dijkstra's algorithm solves the single-pair, single-source, and single-destination shortest path problems.
# Bellman-Ford algorithm solves single source problem if edge weights may be negative.

http://en.wikipedia.org/wiki/Shortest_path_problem

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing. An equivalent algorithm was developed by Edward F. Moore in 1957.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.

Here is the Pseudocode:
shortestPath(Graph, source){
for each vertex v in Graph {
dist[v] = infinity;
previous[v] = NULL;
}
dist[source] = 0 ;
for all neigbors of source {
add to Quene
}
while Quene is not empty {
u = remove from Quene;

for each neighbor v of u {
length = dist[u] + path(u, v);
if (length < dist[v]) {
dist[v] = length;
previous[v] = u;
}
}
return Graph;
}
}


http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm