Shortest Path Algorithm - Part 1

 

•It is exactly what it sounds like!

•Definition: Given a weighted, directed graphs G = (V, E), with weight function w .Finding a the path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

•Variants

1.Single- source shortest - paths problem: Dijkstra's algorithm, Bellman ford algorithm

2.Single - pair shortest - path problem: A* search

3.All - pairs shortest - paths problem: Floyd–Warshall algorithm.

Why do we need it?

Because it is applicable to everyday lives!

Single- source shortest - paths problem

In which we have to find the shortest paths from a source vertex v to all other vertices in the graph. 

Initialization

 INITIALIZE-SINGLE-SOURCE(V, s)

1. for each v Î V

2.       do d[v] ← ¥

3.             p[v] ← NIL

4.d[s] ← 0

Relaxation

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

      we can improve the shortest path to v

      Þ d[v]=d[u]+w(u,v)

      Þ p[v] ← u

 

•Lemma 1: Optimal Substructure

The subpath of any shortest path is itself a shortest path.

•

•Lemma 2: Triangle inequality

If δ(u,v) is the shortest path length between u and v, 

                         δ(u,v) ≤ δ(u,x) + δ(x,v)