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

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей] - C++

Восстановить пароль Регистрация
 
barselona1994
0 / 0 / 0
Регистрация: 04.10.2012
Сообщений: 88
01.05.2013, 13:00     Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей] #1
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует кратчайший путь между ними или нет.
Формат входных данных
В первой строке входного файла записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j), в которой число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100.
Формат выходных данных
Выведите N строк по N чисел: j-ое число в i-ой строке должно быть равно 0, если путь из i в j не существует, 1 - если существует кратчайший путь, и 2 - если существует путь сколь угодно маленького веса.

Может кто может подсказать как решать данную задачу, именно для циклов с отрицательными весами....очень нужно
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2013, 13:00     Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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