Single Source Shortest Path

 

Suppose G be a weighted directed graph where a minimum labeled w(u, v) associated with each edge (u, v) in E, called weight of edge (u, v). These weights represent the cost to traverse the edge. A path from vertex u to vertex v is a sequence of one or more edges.

  <(v1,v2), (v2,v3), . . . , (vn-1, vn)> in E[G] where u = v1 and v = vn

The cost (or length or weight) of the path P is the sum of the weights of edges in the sequence.

The shortest-path weight from a vertex uÎV to a vertex vÎV in the weighted graph is the minimum cost of all paths from u to v. If there exists no such path from vertex u to vertex v then the weight of the shortest-path is ∞.

 

Variant of single-source shortest problems

  1. Given a source vertex, in the weighted diagraph, find the shortest path weights to all other vertices in the digraph.
  2. Given a destination vertex, t, in the weighted digraph, find the shortest path weights from all other vertices in the digraph.
  3. Given any two vertices in the weighted digraph, find the shortest path (from u to v or v to u).

 

Negative-Weight Edges

The negative weight cycle is a cycle whose total is negative. No path from starting vertex S to a vertex on the cycle can be a shortest path. Since a path can run around the cycle many, many times and get any negative cost desired. in other words, a negative cycle invalidates the noton of distance based on edge weights.

 

Relaxation Technique

This technique consists of testing whether we can improve the shortest path found so far if so update the shortest path. A relaxation step may or may not decrease the value of the shortest-path estimate.

The following code performs a relaxation step on edge(u,v).

 

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

 

Diagram

 

Single Source Shortest Problem

Given a weighted graph G, find a shortest path from given vertex to each other vertex in G. Note that we can solve this problem quite easily with BFS traversal algorithm in the special case when all weights are 1. The greedy approach to this problem is repeatedly selecting the best choice from those available at that time.