Идея алгоритмом Флойда — Уоршалла, состоит в следующем. Будем рассматривать последовательность матриц смежности. В этой матрице элемент с индексами (i,j) равен +∞, если в графе нет ребра, ведущего из вершины i в вершину j. В противном случае элемент содержит длину ребра (расстояние) от вершины i к вершине j. Имея эту начальную матрицу в качестве матрицы G0, будем получать далее последовательность матриц G1, G2,Gn, используя формулу
Gk(i,j) = min(Gk-1(i,j), Gk-1(i,k-1) + Gk-1(k -1, j)) .
В этой формуле считается, что если вершины i и j не соединены дугой, то соответствующий элемент матрицы Gk(i,j) содержит бесконечно большое значение +∞, операции с которым подчиняются естественным правилам: для любого значения а (конечного или бесконечного) а + ∞ = ∞, min(a, ∞) = а.
Кроме матрицы длин кратчайших путей G надо получить еще и матрицу направлений D для того, чтобы можно было определить сами найденные кратчайшие пути. Ее можно получать сходным способом. В этой матрице элемент Dk(i,j) равен номеру начальной промежуточной вершины на кратчайшем пути из вершины i в вершину j, проходящему через промежуточные вершины из множества {0, 1,... k-1}. Ясно, что начальная матрица направлений D0 совпадает с исходной матрицей смежности графа, в которой элемент с индексами (i,j) содержит значение j, если имеется ребро, ведущее из вершины i в вершину j, и содержит -1, если такого ребра нет. В дальнейшем, при вычислении матрицы кратчайших путей, как только обнаруживается, что элемент Gk(i,j) следует заменить суммой Gk-1(i,k-1) + Gk-1(k -1, j), элемент Dk(i,j) меняется на Dk-1(i,k-1). Таким образом, в конце концов в матрице Dn будут содержаться направления по всем кратчайшим путям между всеми парами вершин в исходном графе.
Итак, имеем алгоритм, реализованный в виде функции getMinPaths. Этот метод получает в качестве аргументов исходный граф G, нагрузку на его дуги, представленную объектом класса Graphweight, и две переменные, в которые в процессе работы алгоритма и будут записаны значения элементов матрицы кратчайших путей и матрицы направлений.
Листинг : Алгоритм нахождения матрицы кратчайших путей и матрицы направлений методом Флойда — Уоршалла
void getMinPaths(const MatrixGraph & G, // Исходный граф
const GraphWeight & w, // Нагрузка на дуги
double ** & P, // Переменные для матрицы путей
int ** & D // ...и для матрицы направлений
) {
int n = G.vertexCount(); // Число вершин графа
// Инициализация матриц.
// В матрицу длин путей записываются длины дуг исходного графа:
Р = new double*[n];
for (int i = 0; i < n; i++) {
double * row = P[i] = new double[n];
for (int j = 0; j < n; j++) { row[j] = w.arcLength(i, j);
}
}
//В матрицу направлений записывается информация о направлениях
// дуг исходного графа (-1, если направление не определено):
D = new int*[n]; for (int i = 0; i < n; i++) {
int * row = D[i] = new int[n];
for (int j = 0; j < n; j++) {
row[j] = (G.hasArc(i, j) ? j : -1);
}
}
// Вычисление кратчайших путей и направлений
//по алгоритму Флойда — Уоршалла
for (int k = 1; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != k-1 && P[i][k-1] < INFINITY && P[k-l][j] < INFINITY P[i] [j] > P[i] [k-1] + P[k-1] [j]) {
P[i][j] = P[i][k-1] + P[k-1][j];
D[i][j] = D[i][k-1];
}}}}}