Вывод пути через матрицу последовательности узлов Алгоритм Флойда

← →
NoDt (2008-11-18 15:42) [0]

НЕ могу понять как через матрицу последовательности получить путь.

← →
NoDt (2008-11-18 15:43) [1]

И так не одной нормальной реализации, не нашёл

← →
Kerk © (2008-11-18 15:47) [2]

В конце работы алгоритма матрица P будет определять кратчайшие пути между всеми парами вершин: значение pij будет равно номеру предпоследней вершины в пути между i и j (либо pij=i, если путь не существует).

http://algolist.manual.ru/maths/graphs/shortpath/floyd.php

← →
NoDt (2008-11-18 15:56) [3]

Читал это вот к примеру:
матрица последовательности

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

то есть если ищем путь от 1 до 5, то получается что обращаемся к А5,1 = 4 А потом как?

← →
TUser © (2008-11-18 17:51) [4]

Алгоритм описан, например, в учебнике

Ахо, Хопкрофт, Ульман. Название забыл.

← →
NoDt (2008-11-18 18:31) [5]

> TUser © (18.11.08 17:51) [4]

Структуры данных и алгоритмы?

← →
blackman © (2008-11-18 18:34) [6]

Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
Ахо-Хопкрофт-Ульман

← →
Denis__ © (2008-11-19 17:25) [7]

Структуры данных и алгоритмы,2001 г.
Ахо-Хопкрофт-Ульман

← →
AlexWlad © (2008-11-19 19:25) [8]

> NoDt (18.11.08 15:42)
>
> НЕ могу понять как через матрицу последовательности получить
> путь.

Если нужна реализация - сообщи адресок, делал для одного студента недавно, скину архивчик с готовым проектом. Делал по студенческой методичке, переводя пример с языка С.

Если нужно "разжевать" - это не ко мне, звиняй...

> делал для одного студента недавно, скину архивчик

Не стыдно? За 30 серебрянников нагадил своей стране и себе тоже? Будм теперь жить в стране с еще одним "специалистом".

← →
AlexWlad (2008-11-20 19:35) [10]

> TUser © (19.11.08 20:43) [9]

Вот только не надо огульных обвинений. Сейчас где только не впаривают "программирование"!!! Даже на абсолютно непрограммерских специальностях.

Наверное оно зачем-то надо. Там, где впаривают. Мне, допустим, не впаривали (в 2003 закончил).

А обвиненияне не огульные. Они основаны на ваших словах. Вы приучаете людей покупать корки. Потом эти люди купят корку по юриспруденции и бдут вас судить. Или по экономике и устроят вам дефолт. Или купят электорат, то есть вас. И чего-нибудь наворотят. Вот увидете.

А вы - за 30 серебрянников.

Вывод пути через матрицу последовательности узлов Алгоритм Флойда Найти похожие ветки