Алгоритм Флойда-Уоршелла на С++

Задача алгоритм Флойда-Уоршелла на С++

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

Над матрицей выполняется некоторое количество итераций. После k-й итерации matrix[i,j] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. Между вершинами пути i и j могут находиться только те вершины, номера которых меньше или равны k. На k-й итерации для вычисления матрицы применяется следующая формула:
matrixk[i,j]=min(matrixk-1[i,j], matrixk-1[i,k] + matrixk-1[k,j])

Входные данные: graph.txt

Первая строка — это количество вершин графа, дальше идут направления рёбер ориентированного графа + вес ребра (третий столбец).

 

Код:

 

Таким нехитрым образом мы познакомились с темой «Алгоритм Флойда-Уоршелла»!

Post Author: Nikulux

Добавить комментарий