Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Parallel Approach to Floyd Warshall Algorithm

As a part of CA Project
by

Jinal Dhruv

on 11 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Parallel Approach to Floyd Warshall Algorithm

Floyd
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
Full transcript