Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Alexzord
0 / 0 / 0
Регистрация: 01.02.2014
Сообщений: 7
1

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

20.10.2014, 23:06. Просмотров 400. Ответов 0
Метки нет (Все метки)

Нужно, имея матрицу смежности графа, получить матрицу кратчайших путей. Для этого решил использовать алгоритм Флойда-Уоршелла.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <fstream>
#include <cstdlib>
 
using namespace std;
 
int main(int argc, char** argv) {
    ifstream in("in.txt");
    int n;
    int INF = 9;
    in >> n;
    n++;
    int g[n][n], d[n][n];
    for (int i = 0; i < n; i++) {
        for(int j=0;j<n;j++){
            in>>g[i][j];
            d[i][j]=0;
        }
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (g[i][k] < INF && g[k][j] < INF)
                    d[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    for (int i = 0; i < n; i++) {
        for(int j=0;j<n;j++){
            cout<<d[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
Возникает проблема: расстояния большие 2 не выводятся. Выводится 0.
Например, ввожу:
3
0 1 9 9
1 0 1 9
9 1 0 1
9 9 1 0

Вывод:
0 1 2 0
1 0 1 2
2 1 0 1
0 2 1 0

Должен вывести:
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0

В чем проблема?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2014, 23:06
Ответы с готовыми решениями:

Алгоритм Флойда - Уоршелла
не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули...

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++)как сделать так,...

Реализовать алгоритм Флойда Уоршелла
Нужна помощь по написанию алгоритма по задаче представленной ниже: Туристическая фирма...

Алгоритм Флойда-Уоршелла (результат работы неправильный)
Задание выглядит так: Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее...

Разработка ПО для решения задачи минимализации задержек пакетов в корпоративной сети алгоритм Флойда-Уоршелла
Задание: Банк имеет а городе 6 крупных отделений, соединенных оптоволоконными линиями передачи....

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.10.2014, 23:06

Не могу найти ошибку в алгоритме Флойда-Уоршелла
Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти...

Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла
Делаю, алгоритм флойда-уоршелла, делаю сам на делфи, но исходники с решением моей проблемы (ну по...

Алгоритм Уоршелла
#include&lt;stdio.h&gt; #include &lt;iostream&gt; const int V = 4; int i,j; void transitiveClosure(int...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.