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

@barselona1994 · Регистрация: 04.10.2012

Author24 — интернет-сервис помощи студентам

У меня есть задание....дан граф, представленный матрицей смежности. Для каждой пары вершин определить, существует ли кратчайший путь между ними или нет. Если существует, то в матрицу смежности вывести 1, если нет, то 0, если путь бесконечно мал вывести -1

C++

#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]);
  }
 
 
 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)
   for (j=0;j<n;++j)
if (d[i][j] > 0) d[i][j]=1;
 
for (i=0;i<n;++i)
   for (j=0;j<n;++j)
if (d[i][j] < 0) d[i][j]=-1;
  
  for (i=0;i<n;++i,printf("\n"))    // вывод на консоль результата
  for (j=0;j<n;++j)
 printf("%d ", d[i][j]);
}

входной файл:

Код

0 2 2
2 0 3
2 3 0

выход:

Код

-1 -1 -1
-1 -1 -1
-1 -1 -1

Но это неверно!
Должно быть:

Код

1 1 1 
1 1 1 
1 1 1

Что я делаю неверно?

Добавлено через 7 минут
Или может у кого есть реализация этого алгоритма для графов с отрицательными весами?

	30.04.2013, 19:08