Алгоритм Флойда-Уоршелла довольно прост (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%...). Если реализовывать на CPU, то программа будет в три цикла и иметь сложность O(N^3).

Но задача стоит в том, чтобы реализовать на GPU(CUDA). Здесь возникает вопрос, о том как произвести распараллеливание программы. На вход нам подается квадратная матрица размера [N][N], содержащая длины кратчайших путей между всеми вершинами графа(вес), для начало без отрицательного веса дуг. Чтобы понять как алгоритм работает на каждом шаге, можно просмотреть на эмуляторе (http://rain.ifmo.ru/cat/view.php/vis/graph-paths/floyd-warshall-2004) .
За основу алгоритма для начала хотел взять пример умножение матриц на разделяемой памяти (shared memory), но матрицу я должен пройти полностью для сравнения N раз и при каждом сравнении результат(если выполняется условие теста) мне нужно было записывать в исходную матрицу в глобальную память. Поэтому как мне более правильно реализовать просмотр матрицы в данном алгоритме, чтобы при следующем просмотре матрицы я обращался уже к измененной матрице с новыми данными?