130 / 70 / 25
Регистрация: 20.03.2014
Сообщений: 261
1

Не могу разобраться, алгоритм Флойда

19.05.2014, 00:40. Показов 1157. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задача такая. На ориентированном графе найти все отрицательные циклы если таковые имеются и вывести их.
Ума не приложу.
Для простого случая сделать получилось, а когда появляется 2-ва отрицательных цикла которые имеют общую вершину на пути вся матрица весов превращается в отрицательную.

Если кто то сталкивался то помогите.
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.05.2014, 00:40
Ответы с готовыми решениями:

Алгоритм Прима-Краскала. Не могу полностью разобраться с кодом
Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы...

Задали работу, не могу разобраться. Используется делфи 10, не могу разобраться, как это сделать
В одномерном массиве, состоящем из n вещественных элементов, вычислить: минимальный элемент массива...

Алгоритм Флойда
Добрый вечер, помогите исправить ошибки в коде. #include <iostream> #include <time.h> #include...

Алгоритм флойда
Здравствйте у меня есть беда. Есть вот такой код по вычеслению кратчайших путей и запоминание...

3
71 / 45 / 24
Регистрация: 11.05.2014
Сообщений: 179
19.05.2014, 00:50 2
http://e-maxx.ru/algo/negative_cycle
0
130 / 70 / 25
Регистрация: 20.03.2014
Сообщений: 261
19.05.2014, 01:39  [ТС] 3
Я там читал.

"После того, как алгоритм Флойда-Уоршелла отработает для входного графа, переберём все пары вершин (i,j), и для каждой такой пары проверим, бесконечно мал кратчайший путь из i в j или нет. Для этого переберём третью вершину t, и если для неё оказалось d[t][t]<0 (т.е. она лежит в цикле отрицательного веса), а сама она достижима из i и из неё достижима j — то путь (i,j) может иметь бесконечно малую длину."

Если можете то на пальцах объясните пожалуйста.

трассировка для 1-й картинки
Кликните здесь для просмотра всего текста

k=0
0 1 ? ? ?
? 0 1 1 1
? ? 0 1 ?
? ? ? 0 -3
1 1 ? ? 0

1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

k=1
0 1 ? ? ?
? ? 1 1 1
? ? ? 1 ?
? ? ? ? -3
1 1 ? ? ?

1 1 1 1 1
2 1 2 2 2
3 3 1 3 3
4 4 4 1 4
5 5 5 5 1

k=2
? 1 2 2 2
? ? 1 1 1
? ? ? 1 ?
? ? ? ? -3
1 1 2 2 2

2 1 2 2 2
2 1 2 2 2
3 3 2 3 3
4 4 4 2 4
5 5 2 2 2

k=3
? 1 2 2 2
? ? 1 1 1
? ? ? 1 ?
? ? ? ? -3
1 1 2 2 2

2 1 2 2 2
2 1 2 2 2
3 3 2 3 3
4 4 4 2 4
5 5 2 2 2

k=4
? 1 2 2 -1
? ? 1 1 -2
? ? ? 1 -2
? ? ? ? -3
1 1 2 2 -1

2 1 2 2 4
2 1 2 2 4
3 3 2 3 4
4 4 4 2 4
5 5 2 2 4

k=5
0 0 1 1 -2
-1 -1 0 0 -3
-1 -1 0 0 -3
-2 -2 -1 -1 -4
0 0 1 1 -2

5 5 2 2 4
5 5 2 2 4
5 5 2 2 4
5 5 2 2 4
5 5 2 2 4


для 2-й картинки(2 отрицательных цикла)
Кликните здесь для просмотра всего текста

k=0
0 1 ? ? ?
? 0 1 1 1
? ? 0 1 ?
? ? ? 0 -3
-3 1 ? ? 0

1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

k=1
0 1 ? ? ?
? ? 1 1 1
? ? ? 1 ?
? ? ? ? -3
-3 -2 ? ? ?

1 1 1 1 1
2 1 2 2 2
3 3 1 3 3
4 4 4 1 4
5 1 1 1 1

k=2
? 1 2 2 2
? ? 1 1 1
? ? ? 1 ?
? ? ? ? -3
-3 -2 -1 -1 -1

2 1 2 2 2
2 1 2 2 2
3 3 2 3 3
4 4 4 2 4
5 1 2 2 2

k=3
? 1 2 2 2
? ? 1 1 1
? ? ? 1 ?
? ? ? ? -3
-3 -2 -1 -1 -1

2 1 2 2 2
2 1 2 2 2
3 3 2 3 3
4 4 4 2 4
5 1 2 2 2

k=4
? 1 2 2 -1
? ? 1 1 -2
? ? ? 1 -2
? ? ? ? -3
-3 -2 -1 -1 -4

2 1 2 2 4
2 1 2 2 4
3 3 2 3 4
4 4 4 2 4
5 1 2 2 4

k=5
-4 -3 -2 -2 -5
-5 -4 -3 -3 -6
-5 -4 -3 -3 -6
-6 -5 -4 -4 -7
-7 -6 -5 -5 -8

5 1 2 2 4
5 1 2 2 4
5 1 2 2 4
5 1 2 2 4
5 1 2 2 4
Миниатюры
Не могу разобраться, алгоритм Флойда   Не могу разобраться, алгоритм Флойда  
0
130 / 70 / 25
Регистрация: 20.03.2014
Сообщений: 261
19.05.2014, 19:51  [ТС] 4
Ни кто не сталкивался?
Мне уже просто кажется что алгоритмом Флойда этого не сделать, а препод требует.
1
19.05.2014, 19:51
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.05.2014, 19:51
Помогаю со студенческими работами здесь

Алгоритм Флойда
Помогите переделать программу вот нашел #include &lt;iostream&gt; const int inf=1E9; using namespace...

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

Алгоритм Флойда
Помогите решить задачу: нужно найти кратчайшее расстояние между любыми двумя городами. всего...

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

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

Алгоритм Флойда-Уоршелла
Народ подскажите , а как реализовать этот алгоритм на Delphi ?


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru