Реализация алгоритма Флойда-Уоршелла на C/C++

Доброго времени суток, друзья! Сегодня моя копилка реализованных алгоритмов на графах пополнится алгоритмом поиска кратчайших путей между всеми вершинами в графе. Для начала перечислю алгоритмы, которые уже опубликованы на сайте.

— Реализация поиска в ширину на графе;
— Реализация поиска в глубину на графе;
— Реализация топологической сортировки и поиска компонент сильной связности;

Реализация обычного алгоритма Флойда-Уоршелла нужна мне для того, чтобы запрограммировать параллельное вычисление этой задачи с помощью библиотеки MPI. Отчет о результатах распараллеливания я напишу уже совсем скоро(я очень на это надеюсь). А сейчас поговорим о стандартном алгоритме Флойда-Уоршелла.

Суть алгоритма Флойда-Уоршелла

Как я упомянул, алгоритм предназначен для нахождения кратчайших путей между всеми вершинами в графе. По сути он представляет собой простой перебор всех путей и выбор из них наименьшего. Перебор осуществляется по так называемой «матрице смежности» размера NxN, где N — количество вершин графа.

На пересечении i-ой строки и j-го столбца матрицы стоит значение веса ребра из вершины i в вершину j. Главная диагональ матрицы смежности это всегда нули, потому что ребер из i-ой вершины в i-ую в графе быть не должно. В том случае, когда между вершинами нет ребра, в матрице будет стоять условная бесконечность(INF).

Реализация алгоритма Флойда-Уоршелла

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

Матрицу смежности удобнее всего хранить в файле в следующем виде: первой строкой количество вершин, затем непосредственно сама матрица. В качестве бесконечно большого расстояния(INF, когда вершины не связаны ребром) взять конкретную константу. В моей реализации она равна 101, это значит, что максимальный вес ребра не может быть больше 100.

Пример файла с матрицей

4
0 10 1 101
10 0 101 5
1 101 0 2
101 5 2 0

Исходный код алгоритма

//matrix - матрица смежности
void originalFloydWarshall(int **matrix, int numberOfVert) {
    //Пробегаемся по всем вершинам и ищем более короткий путь
    //через вершину k
    for(int k = 0; k < numberOfVert; k++) {
        for(int i = 0; i < numberOfVert; i++) {
            for(int j = 0; j < numberOfVert; j++) {
                //Новое значение ребра равно минимальному между старым
                //и суммой ребер i <-> k + k <-> j (если через k пройти быстрее)
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
            }
        }
    }

    return;
}

Пример работы с алгоритмом

#include <iostream>
#include <algorithm>
#include <fstream>

//Максимальное значение веса = 100
#define INF 101

using namespace std;

void printMatrix(int** matrix, int numberOfVert) {
    for(int i = 0; i < numberOfVert; i++) {
        for(int j = 0; j < numberOfVert; j++) {
            if(matrix[i][j] == INF) {
                cout << "INF" << " ";
            }
            else {
                cout << matrix[i][j] << " ";
            }
        }
        cout << endl;
    }
}

//matrix - матрица смежности
void originalFloydWarshall(int **matrix, int numberOfVert) {
    //Пробегаемся по всем вершинам и ищем более короткий путь
    //через вершину k
    for(int k = 0; k < numberOfVert; k++) {
        for(int i = 0; i < numberOfVert; i++) {
            for(int j = 0; j < numberOfVert; j++) {
                //Новое значение ребра равно минимальному между старым
                //и суммой ребер i <-> k + k <-> j (если через k пройти быстрее)
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
            }
        }
    }
    
    return;
}

int main(int argc, char** argv) {
    ifstream file("matrix");
    int numberOfVert;
    file >> numberOfVert;
    cout << numberOfVert << endl;
    
    //Матрица смежности с весами ребер графа(101 - ребра нет, 0 ребро в себя)
    int **matrix = (int**)malloc(sizeof(int)*numberOfVert);
    for(int i = 0; i < numberOfVert; i++) {
        matrix[i] = (int *) malloc(sizeof(int) * numberOfVert);
    }
    
    //Считываем матрицу весов ребер
    for(int i = 0; i < numberOfVert; i++) {
        for(int j = 0; j < numberOfVert; j++) { file >> matrix[i][j];
        }
    }
    
    file.close();
    
    cout << "Old matrix" << endl;
    printMatrix(matrix, numberOfVert);
    
    originalFloydWarshall(matrix, numberOfVert);
    
    cout << "New matrix" << endl;
    
    printMatrix(matrix, numberOfVert);
    
    return 0;
}

Заключение

Обычный алгоритм Флойда-Уоршелла реализуется очень просто, но работает очень долго на больших матрицах. Идеальный кандидат для того, чтобы отдать его на растерзание библиотеке MPI. На сегодня у меня все, спасибо за внимание!