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

C++   7 января 2012  Автор статьи:  

Задан взвешенный ориентированный граф из N вершин. Требуется построить для этого графа матрицу кратчайших путей между всеми парами вершин.

Входные данные:

В первой строке записано натуральное число N (1\le N\le 100). В каждой из следующих N строк записано по N чисел – матрица D весов ребер графа. Все веса – целые числа, по модулю не превосходящие 1000. Если некоторый элемент матрицы равен 1001, то это означает, что соответствующей дуги в графе нет.

Выходные данные:
Если в графе есть циклы отрицательного веса и потому не все кратчайшие пути определены, вывести «INCORRECT INPUT». В противном случае вывести матрицу кратчайших путей графа. Если между какими-то вершинами пути не существует, вместо расстояния вывести слово «NO».

Реализация решения

Подробный разбор алгоритма см. в этой статье.

[cc lang=»cpp» lines=»-1″]
#include
const int inf=1E9;
using namespace std;
int main()
{
int n,i,j,k,d[100][100];
scanf(«%d»,&n);
for (i=0;iАвтор статьи – Сухов Сергей

Научиться программировать

  • на Delphi

  • на Java

  • на C++