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

@zubi · Регистрация: 19.08.2014

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

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

C++

#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;
}

@MrLinch · 23.08.2014, 16:29

Попробуй приписать цикл таким образом:

C++

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 · 23.08.2014, 17:41 **[ТС]**

попробовал но не получается

@DieMore · 23.08.2014, 22:10

Вообще,для данной задачи лучше использовать алгоритм Дейкстры или Форда-Беллмана. Они быстрее и потребляют меньше памяти.

C++

#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;
}

Должно работать.

Новые блоги и статьи
Как написать микросервис на Go/Golang InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .
Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .	UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела volvo 13.01.2025 В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения: / / ==UserScript== / / @name CF_DefaultLangSelect / / . . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .

@zubi 0 / 0 / 0 Регистрация: 19.08.2014 Сообщений: 8
	23.08.2014, 17:41 [ТС]	3
	попробовал но не получается 0

	23.08.2014, 22:10

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

Решение