﻿﻿﻿﻿﻿ Floyd's Algorithm for shortest path - Coddicted

# Floyd’s Algorithm for shortest path

Based on Dynamic Programming

• It is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge(but without negative cycle)(shortest path between all pairs)
• The single execution of the algorithm will find the lengths(summed weights) of the shortest paths between all pairs of vertices. though it does not return details of the themselves.
• Also used for finding transitive closure

Algorithm details
Consider a graph G with vertices V numbered 1 through N. Further consider a function shortestPath(i,j,k) that return the shortest possible path from i to j using vertices only from the set {1,2,3,..,k} as intermediate point along way.

shortestPath(i,j,k) : returns shortest path from i to j using vertices from the set {1,2,..,k}

Goal: our goal is to find the shortest path from i to j using only vertices from the set {1,2,..,k,k+1}

Observation I:
for each of these pair of vertices, the true shortest path could be either
1. a path that only uses vertices from the set {1,..,k}
2. a path that goes from i to k+1 and then from k+1 to j

Observation II:
we know the best path from i to j that only uses vertices {1,..,k} is defined by shortestPath(i,j,k) and it is clear that if there were a better path from i to k+1 to j, then the length of this path would be concatenation of the shortest path from i to k+1 using vertices in {1,…,k} and the shortest path from k+1 to j (again, using vertices in {1,…,k})

shortestPath(i,j,0) = w(i,j)
where w(i,j) is weight of vertex from i to j.
and recursive case is

shortestPath(i,j,k) = min(shortestPath(i,j,k-1), shortestPath(i,k,k-1)+shortestPath(k,j,k-1))