Shortest path Algorithms

In a shortest path problem we are given a weighted graph where each edge has an associated numerical value, called the weight of the edge.The weights are often used to represent time, cost, penalties or any other quantity that accumulates linearly along a path and that one wishes to minimize.

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.

For each vertex v Є V, an attribute d[v] is maintained which is an upper bound on the weight of a shortest path from source s to v.

d[v] – shortest path estimate

The shortest path estimates and predecessors are initialized by the following O(V) time procedure.

INITIALIZE-SINGLE-SOURCE (G,s)

for each vertex v Є V[G]

     do d[v] <-- ∞

         π[v] <-- NIL

                     d[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].

Relaxation

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

Relax (u,v,w)

if d[v] > d[u] + w(u,v)

  then d[v] <-- d[u] + w(u,v)

   π[v]  <-- u