Параллельные алгоритмы на графах

При исследовании параллельных алгоритмов на графах будем представлять графы матрицами смежности. Мы займемся некоторыми замечательными связями между матричными операциями над матрицами смежности и свойствами соответствующих графов.

Параллельный алгоритм поиска кратчайшего пути

Определим матрицу смежности взвешенного графа следующим образом:

На рис. 9.7 изображен взвешенный граф и его матрица смежности. В матрице смежности представлены прямые пути между вершинами графа, т. е. пути, состоящие из одного ребра. Нас интересуют кратчайшие пути по графу, состоящие из произвольного числа ребер. Попробуем восстановить их по матрице смежности. В исходной матрице А = А1 содержатся длины кратчайших путей из нуля или одного ребра. В матрице AJ будут записаны длины кратчайших путей из не более чем J ребер. Ясно, что в матрице AN~1 будут записаны длины всех кратчайших путей с произвольным числом ребер, потому что всякий путь из N и более ребер содержит цикл, а значит, кратчайший путь должен содержать не более N - 1 ребер.

Взвешенный граф и его матрица смежности

Рис. 9.7. Взвешенный граф и его матрица смежности

Подумаем, как можно построить матрицу А2 по матрице А1. Кратчайший путь из двух ребер между вершинами х и у проходит еще в точности через одну вершину. Например, всякий путь длины два между вершинами А и Е проходит либо через вершину В, либо через вершину D. Сравнив сумму весов ребер А В и BE с суммой весов ребер AD и DE, видим, что путь через вершину D короче пути через вершину В. В общем случае, если посмотреть на сумму весов ребер А* и Е*, где * пробегает все вершины от А до / (за исключением самих вершин А и Е), то минимальное значение суммы весов будет давать длину кратчайшего пути из двух или менее ребер. Отсюда получаем

Применив эту процедуру к матрице смежности на рис. 9.7, получим матрицу, показанную на рис. 9.8.

Матрицу А3 можно построить по матрицам А1 и А2, заметив, что кратчайший путь из трех или менее ребер должен состоять из кратчайшего пути из двух или менее ребер, за которым следует кратчайший путь из одного или менее ребер и наоборот. Матрицу А4 можно построить либо по матрицам А и А', либо только по матрице А . Поэтому до конца добраться легче, вычисляя матрицы А , А , А , ..., А , где Л" - первая степень двойки, которая превышает число вершин, уменьшенное на 1. Все кратчайшие рас- стояния в графе с рис. 9.7 получим, подсчитав матрицу А .

Матрица^для взвешенного графа с рис. 9.7

Рис. 9.8. Матрица^2 для взвешенного графа с рис. 9.7

Параллельный подсчет кратчайших расстояний в графе можно реализовать на основе этих матричных операций. Заменив в алгоритме умножения матриц сложение операцией взятия минимума, а умножение сложением, получим алгоритм, вычисляющий нужные нам матрицы. Применение модифицированного алгоритма матричного умножения к матрицам А1 и А1 даст матрицу А2, а к матрицам А2 и А2 - матрицу А4. Теперь параллельный алгоритм подсчета кратчайших расстояний превращается просто в параллельный алгоритм умножения матриц, поэтому анализ последнего применим и в данном случае.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >