Implementation of Floyd-Warshall algorithm in CUDA
$30-70 USD
Paid on delivery
Implementation of Floyd-Warshall algorithm in CUDA, for computing the optimal path among all pairs of vertices (All Pairs Shortest Path) in a directed graph with non negative edge length.
Consider a graph whose set of vertices is {1, 2,?.,n}.
The input of the program will be an n*n matrix A, float type, where
A[i][j]=0 when i==j
cost of the edge (i,j)
Inf for non existing edges
Output:
a) n*n matrix D(float type) where the D[i][j] element will be the sortest path from the node i to node j or Inf if no such path exists.
b) n*n matrix int Q where the Q[i][j] element will be the intermediate node that exists between the nodes i and j, or 0 if the edge( i, j) is the sortest path from i to j, or Inf if there is no such path.
The pair of matrices D and Q should allow the reconstruction of the sequence of the vertices that form the optimal path for every pair (i, j).
n=2^q , q=8......12
We also want to estimate the time that the program needs for the computation in these two cases:
a) including the time for the data transmission from and to the GPU
b) not including the time for the data transmission from and to the GPU
Project ID: #2707026
