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.

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

## No comments:

## Post a Comment