Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
zubi
0 / 0 / 0
Регистрация: 19.08.2014
Сообщений: 8
#1

Не могу найти ошибку в алгоритме Флойда-Уоршелла - C++

23.08.2014, 16:15. Просмотров 760. Ответов 3
Метки нет (Все метки)

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины s в вершину t.
Формат входных данных
В первой строке заданы три числа: число вершин в графе N ≤50, номера вершин s и t. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от 0 до 1000000, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.
Формат выходных данных
Выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<stdio.h>
#include<cmath>
 
using namespace std;
 
int main(){
    freopen("input.txt","r",stdin);
    int d[55][55],n,s,t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>d[i][j];
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(d[i][k]>0 && d[k][j]>0)
                    d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
    cout<<d[s][t];  
    return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2014, 16:15     Не могу найти ошибку в алгоритме Флойда-Уоршелла
Посмотрите здесь:

C++ Не могу найти ошибку.
C++ Алгоритм Флойда - Уоршелла
Алгоритм Флойда-Уоршелла (результат работы неправильный) C++
Найти слова, повторяющиеся более одного раза, не могу найти ошибку C++
C++ Алгоритм Флойда–Уоршелла
C++ Массивы. Посчитать количество положительных, найти минимальное, удалить строку с минимальным (Не могу найти ошибку)
В линейном алгоритме выдает ошибку: 1 unresolved externals C++
Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла C++
Нахождение значения функции в заданной точке, найти ошибку в алгоритме C++
не могу найти ошибку C++
C++ Найти ошибку в разветвляющемся алгоритме
C++ Не могу найти ошибку!

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrLinch
12 / 10 / 6
Регистрация: 23.12.2012
Сообщений: 51
23.08.2014, 16:29     Не могу найти ошибку в алгоритме Флойда-Уоршелла #2
Попробуй приписать цикл таким образом:
C++
1
2
3
4
5
for(k = 0; k < n; ++k)
    for(i = 0; i  < n; ++i)
        for(j = 0; j < n; ++j)
            if(d[i][j] >= d[i][k] + d[k][j]) 
                d[i][j] = d[i][k] + d[k][j];
zubi
0 / 0 / 0
Регистрация: 19.08.2014
Сообщений: 8
23.08.2014, 17:41  [ТС]     Не могу найти ошибку в алгоритме Флойда-Уоршелла #3
попробовал но не получается
DieMore
3 / 3 / 2
Регистрация: 21.08.2014
Сообщений: 17
23.08.2014, 22:10     Не могу найти ошибку в алгоритме Флойда-Уоршелла #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вообще,для данной задачи лучше использовать алгоритм Дейкстры или Форда-Беллмана. Они быстрее и потребляют меньше памяти.
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
#include<iostream>
#include<stdio.h>
#include<cmath>
 
using namespace std;
 
int main(){
    freopen("input.txt","r",stdin);
    int d[55][55],n,s,t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>d[i][j];
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) {
                if(d[i][k]>0 && d[k][j]>0) {
                    if (d[i][j] == -1) d[i][j] = d[i][k] + d[k][j];
                    else d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
                }
            }
    cout<<d[s][t];  
    return 0;
}
Должно работать.
Yandex
Объявления
23.08.2014, 22:10     Не могу найти ошибку в алгоритме Флойда-Уоршелла
Ответ Создать тему
Опции темы

Текущее время: 13:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru