The weight of path p = < v0, v1,….vk> is the sum of the weights of its constituent edges.
Given a weighted graph and two vertices u and v, we want to find a path of minimum total weight between u and v.
–Length of a path is the sum of the weights of its edges.
We will focus on Single source shortest paths problem: given a graph G = (V,E), we want to find a shortest path from a given source vertex s Є V to each vertex v Є V.
Shortest Path Properties
Property 1: A sub path of a shortest path is itself a shortest path.
Property 2: There is a tree of shortest paths from a start vertex to all the other vertices.
The shortest path algorithms use the technique of relaxation.
d[v] – shortest path estimate
The shortest path estimates and predecessors are initialized by the following O(V) time procedure.
for each vertex v Є V[G]
do d[v] <-- ∞
π[v] <-- NILd[s] <-- 0
Relaxing and edge (u,v) – consists of testing whether the shortest path to v found so far can be improved by going through u. If so d[v] and π[v] values should be updated.
A relaxation step may decrease the value of the shortest path estimate d[v].
d[v] > d[u] + w(u,v) d[v] ≤ d[u] + w(u,v)
d[v] is changed by relaxation d[v] is unchanged by relaxation
if d[v] > d[u] + w(u,v)
then d[v] <-- d[u] + w(u,v)
π[v] <-- u