Shortest Path Problem


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

One thought on “Shortest Path Problem”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s