## 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.

<(*v*_{1},*v*_{2}), (*v*_{2},*v*_{3}),
. . . , (*v*_{n-1}, *v*_{n})> in E[G] where u = *v*_{1}*
*and *v = v*_{n}

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

- Given a source vertex, in the weighted diagraph, find the shortest path
weights to all other vertices in the digraph.
- Given a destination vertex, t, in the weighted digraph, find the shortest
path weights from all other vertices in the digraph.
- 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.