**Floyd**

Warshall

Algorithm

Warshall

Algorithm

**Thank you for your attention!**

Floyd Warshall Algorithm is also known as

"All Pair Shortest Path" Algorithm!

Why Map Reduce Pattern and How it helps?

**Summary**

MapReduce is a programming model for processing large data sets with a parallel, distributed algorithm on a cluster.

From the observations I believe that the best use of parallel implementation of all pair shortest path algorithm is for large datasets or graphs. The speedups can only be observed with large adjacency matrices.

is here

for each vertex v

dist[v][v] = 0

for each edge (u,v)

dist[u][v] = w(u,v) // the weight of the edge (u,v)

for k from 1 to |V|

for i from 1 to |V|

for j from 1 to |V|

if dist[i][k] + dist[k][j] < dist[i][j] then

dist[i][j] = dist[i][k] + dist[k][j]

open-source software framework that supports data-intensive distributed applications.

Made for Big Data.

Though Java code is most common, any programming language can be used with "streaming" to implement the "map" and "reduce" parts of the system.

HDFS and Map-Reduce ==> Handling Node Failure automatically.

Run on Block by Block Basis.

Input, Map, Shuffle and Sort, Reduce, Output.

Sequential Algorithm:

For each value of k that is the count of inter mediatory nodes between node i and j the algorithm computes the distances between node i and j and for all k nodes between them and compares it with the distance between i and j with no inter-mediatory nodes between them.

Parallelizing all pair shortest path algorithm is a challenging task considering the fact that the problem is dynamic in nature.

for k = 0 to N-1

for i = local_i_start to local_i_end

for j = 0 to N-1

Iij (k+1) = min (Iij(k), Iik(k) + Ikj(k))

Endfor

Endfor

endfor

The Floyd-Warshall Parallel algorithm [3]

Let's make it

efficient!

What is

All Pair Shortest Path

Dijkstra Algorithm

Single Source Shortest Path

Bellman Ford Algorithm

Relax first!

Now it's time to think about "All Pairs Shortest Paths"

Path to Floyd Warshall Algorithm

How it works?

What is it's complexity?

Solve it using Dijkstra's Algorithm

So, this does not work for

negative edges. what now?

O (|V| |E|) is the worst case

complexity.

The closest node in the graph can have shorter path passing through another node!

Don't use Priority Queues.

Step 1: initialize graph

for each vertex v in vertices:

if v is source then distance[v] := 0

else distance[v] := infinity

Step 2: relax edges repeatedly

for i from 1 to size(vertices)-1:

for each edge (u, v) with weight w in edges:

if distance[u] + w < distance[v]:

distance[v] := distance[u] + w

predecessor[v] := u

Step 3: check for negative-weight cycles

for each edge (u, v) with weight w in edges:

if distance[u] + w < distance[v]:

error "Graph contains a negative-weight cycle"

So, error indicates there is a negative cycle.

A negative cycle can be found with Bellman-Ford’s algorithm!

Greedy Approach

If no negative edges, then apply Dijkstra Algo. n times ==> O(|V|^3)

Same way, Bellman Ford Algo. gives O(e(|V|^2)).

Can we make it better?

Let's try Dynamic Approach.

Understanding Floyd Warshall Algorithm

compares all possible paths through the graph between each pair of vertices

It is able to do this with only O(|V|^3) comparisons in a graph. This is remarkable considering that there may be up to O(|V|2^) edges in the graph, and every combination of edges is tested.

shortestPath(i,j,k)

our goal is to find the shortest path from each i to each j using only vertices 1 to k + 1.

Can we reduce complexity of Floyd Warshall Algorithm any more?

There's always a scope of betterment and Dynamic Programming is not an exception!

Parallel Approach for Floyd Warshall Algorithm

It then considers the minimum distance among the two distances calculated above.

Exploiting the memory hierarchy

Loop Interchange

Loop Tiling

Reference: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.5378&rep=rep1&type=pdf

Here local_i_start to local_i_end are the indexes decided by the partition size of the adjacency matrix i.e. value of N/P

T=((N^3)/P)+NlogP(ts+twN)

Somewhat better time complexity!

2 minutes on Hadoop..

Reference: http://hadoop.apache.org/core