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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
const int inf=1E9;
using namespace std;
int main()
{  
 int n,i,j,k,d[100][100];
 scanf("%d",&n);
 for (i=0;i<n;++i)
  for (j=0;j<n;++j)
  {
   scanf("%d",&d[i][j]);
   if (i==j) d[i][j]=min(d[i][j],0);
   if (d[i][j]==1001) d[i][j]=inf;
  }
 for (k=0;k<n;++k)
  for (i=0;i<n;++i)
   for (j=0;j<n;++j)
    if (d[i][k]<inf && d[k][j]<inf) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
 for (i=0;i<n;++i)
  if (d[i][i]<0) { printf("INCORRECT INPUT"); return 0; }
 for (i=0;i<n;++i,printf("\n"))
  for (j=0;j<n;++j)
   if (d[i][j]==inf) printf("NO "); else printf("%d ",d[i][j]);
}

Автор статьи – Сухов Сергей

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

  • на Delphi

  • на Java

  • на C++