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

### Like this:

Like Loading...

*Related*

hmm interesting site. There are very few things like my gentle recognition Good joke 🙂 What did the sailor say when he saw a boat loaded with ewes? Sheep ahoy!