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

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

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

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

23.08.2014, 16:15. Просмотров 882. Ответов 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;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2014, 16:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Не могу найти ошибку в алгоритме Флойда-Уоршелла (C++):

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

Алгоритм Флойда–Уоршелла - C++
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++) как сделать так, чтобы алгоритм нахождения кратчайшего...

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

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

Найти ошибку в разветвляющемся алгоритме - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; int main() { int xP,xK,step,x; float f,a,b,c; cout&lt;&lt;&quot;Input...

Нахождение значения функции в заданной точке, найти ошибку в алгоритме - C++
С помощью численных методов надо найти значение функции в точке. Есть файл (у нас это database.txt) со значением функции в разных точках....

3
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];
0
zubi
0 / 0 / 0
Регистрация: 19.08.2014
Сообщений: 8
23.08.2014, 17:41  [ТС] #3
попробовал но не получается
0
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;
}
Должно работать.
1
23.08.2014, 22:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2014, 22:10
Привет! Вот еще темы с ответами:

В линейном алгоритме выдает ошибку: 1 unresolved externals - C++
пишу на Visual C++ 2012 (сюда обратился так как знающего люду больше) выдает ошибку - помогите кто чем может ошибка такая: fatal error...

Найти слова, повторяющиеся более одного раза, не могу найти ошибку - C++
#include &lt;iostream&gt; using namespace std; void obr1(char **s, char **mas, int n, int m) { int i; int k; char *tm; for(i...

Массивы. Посчитать количество положительных, найти минимальное, удалить строку с минимальным (Не могу найти ошибку) - C++
// Заданы матрицы X(8;4),Y(5;5),Z(6;9). // Для каждой из матриц определить строку, в которой находится наименьшее // количество...

Не могу найти ошибку - C++
Ребята, в общем, пишу код более-менее нормального меню, переключаться вверх/вниз с помощью стрелок! Не надо говорить про аппликацию, это...


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

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

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