shortest path problem
Posted by Vinod on May 19, 2006
weight function for a weighted direct graph G=(V,E) ,W:E->R mapping from edges to real valued weights.
the weight of a path p=(v0,v1,v2,v3…….,vn) is given by the sum of its constituent edges.
the length of shorest path is given by l(u,v)=min(w(p)) if there is a path from
u to v; other wise l(u,v)=infinity
shortest path from vertex u to vertex v can be defined as that path p whose
w(p)=l(u,v);
the types of shortest path problems are:
1) single source shortest path problem: Ths is to find the shortest path from a given source vertex 's' to all other vertices in V
2)single destination shortest path prolem: This is to find the shortest paths to a vertex v from all other vertirces in V
3)single pair shortest path problem:This is to find the shortest path from a vertex u to a vertex v for a given pair of vertices (u,v) which belong to V
4)All-pairs shortest paths problem:This is to find the shortest paths from vertex u to vertex v for each pair of (u,v) which are in V
