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

Question

есть такой граф:

0 8 0 0 10
8 0 4 0 0
0 4 0 6 16
0 0 6 0 2
10 0 16 2 0
и есть такой код, для нахождения кр. путей между вершинами

for (k = 0; k < n; ++k)
 {
 for (i = 0; i < n; ++i)
 for (j = 0; j < n; ++j)
 if ((dist[i, k] * dist[k, j] != 0) && (i != j))
 if ((dist[i, k] + dist[k, j] < dist[i, j]) || (dist[i, j] == 0))
 dist[i, j] = dist[i, k] + dist[k, j];
 }

не могу понять, что не так, почему к примеру расстояние между 5 и 2 = 18 а не 12 и тд. . .

Аленка Руденок · Accepted Answer

http://habrahabr.ru/post/119158/ здесь вроде проще

Саша Дроздов · Answer

Ой не сюда вопрос. Сходи на www.exponenta.ru там на форуме пошарься - поспрашивай народ. Там народ ой продвинутый в математике - точно скажет...

Алексей Машнин · Answer

#include
#include
#include

using namespace std;

int main()
{
long n;
cin >> n;
vector < vector > a(n, vector (n));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(a[i][j] > a[i][k] + a[k][j])
{
a[i][j] = a[i][k] + a[k][j];
}
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout