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

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

01.05.2013, 13:00. Просмотров 1268. Ответов 0
Метки нет (Все метки)

Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует кратчайший путь между ними или нет.
Формат входных данных
В первой строке входного файла записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j), в которой число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100.
Формат выходных данных
Выведите N строк по N чисел: j-ое число в i-ой строке должно быть равно 0, если путь из i в j не существует, 1 - если существует кратчайший путь, и 2 - если существует путь сколь угодно маленького веса.

Может кто может подсказать как решать данную задачу, именно для циклов с отрицательными весами....очень нужно
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.05.2013, 13:00
Ответы с готовыми решениями:

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

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

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

Нахождения кратчайших путей между всеми парами вершин графа
Подскажите как можно улучшить алгоритм Флойда-Уоршелла что-бы он верно работал если длина некоторых...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.05.2013, 13:00

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Поиск кратчайших путей из одного источника для неориентированного графа
Дорогие программисты! Прошу вас помочь мне в очень срочном деле! Очень нужен код программы,...

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

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

Поиск кратчайших путей в графе
Владислав Исенбаев — двукратный чемпион Урала по программированию, вице-чемпион TopCoder Open 2009,...


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

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

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