 Back |
 Table
of contents |
 Next |
Single-source Shortest path
In this chapter we
try to solve problems called shortest - path problems stated
as follows:
Optimal substructure of a shortest path:
Lemma1:(Subpaths
of shortest paths are shortest paths)
Corrolary
:
Relaxation:
We are given a weighted,directed graph G=(V,E),with weight function
w:->R mapping edges to real valued weights.The weight of
path p=<v0,v1,...........,vk> is the sum of weights of
its edges.The shortest -path weight from u tov is defined
by
delta(u,v)=min{w(P):u->v} if there is a path from u to v
=0 otherwise
A shortest-path from vertex v to u is defined as any
path p with w(P)=delta(u,v).
Negative-weight edges:
If a graph
G=(V,E) contains no negative-weight cycles reachable from source s,then
for all v in V the shortest path is well defined.If there is a negative
weight cycle reachable it is not very well defined.Dijkstra's algorithm
,assumes that all edges in the input graph are non negative.Others
such as Bellman-Ford algorithm,allow negative weight edges in
the input graph and produce a correct result as long as no negative weight
edges are
rechable from source vertex.
Shortest-path
algorithms exploit the property that a shortest path between two
vertices contains other shortest path between it.
Given a weighted,directed graph G=(V,E) with weight function w:E-> R ,let
p=<v1,v2,........,vk> be a shortest path
from vertex v1 to vk and for any i and j such that
1<=i<=j<=k,let pij =<vi,vi+1,.............,vj>be a subpath
of p from vertex vi to vj then pij is
the shortest path for vi to vj .
Let G= (V,E) be a weighted directed graph with weight function w :E->R
.Suppose that the shortest path from source s to vertex v
can be decomposed into s -> u (through p*) ->
v for some vertex u and path p*.Then,the weight of the
shortest path from s to v is
delta (s,v) = delta(s,u) + w(u,v)
The process
of relaxing an edge (u,v) consists of
testing whether we can improve the shortest path to v