Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Поиск в графе

AZIZE © (2007-07-25 16:12:00)
Люди! нужно максимум различных способовнахождения максимального и минимального пути в графе от вершины А к вершине В;
В случае максимального, исключать циклический поиск;
Методы Краскала, Прима, в ширину и в глубину можно не предлагать они уже реализованы
заранее спасибо

MBo (2007-07-26 11:40:00) [1]
>это легко обходится плюсованием ко всем весам константы так, чтоб минимальный был 0

Ну прямо так просто? Контрпример:
A-B 5
A-C 2
C-D -1
D-B 3
кратчайший путь из A в B - A_C_D_B
а если добавить ко всем весам 1, чтобы занулить СD, то Дейкстра получит "левый" кратчайший путь A_B

Конечно, есть модификации Дейкстры (например, с потенциалами), решающие проблему отриц. весов, тем не менее она существует...

AZIZE (2007-07-26 11:32:00) [2]

> это легко обходится плюсованием ко всем весам константы
> так, чтоб минимальный был 0

данный вариант нериемлем, т. к. в случае поика минимума необходимо найти действительно минимальный вес (отрицательный)
да и ещё одно условие все веса лежат в диапазоне [-1..1]

Вася Правильный (2007-07-26 11:13:00) [3]

> алг. Дейкстры для отриц. весов непригоден

это легко обходится плюсованием ко всем весам константы так, чтоб минимальный был 0

MBo (2007-07-26 10:50:00) [4]
>весов? и чего там сложного?
Ну например, алг. Дейкстры для отриц. весов непригоден, а Флойда - работает (правда, он для всех пар вершин сразу)

Вася Правильный (2007-07-26 10:43:00) [5]

> сложность задачи в наличии отрицательных рёбер

весов? и чего там сложного?
или все-таки направлений?

AZIZE (2007-07-26 09:56:00) [6]

> MBo © (26.07.07 08:44) [10]

за ссылку спасибо

AZIZE (2007-07-26 09:54:00) [7]

> P.S. как "в ширину и в глубину" связано с мин. путями -
> не уловил :(

есть алгоритмы поиска в ширину и глубину для построения кратчайшего пути, для этого просто необходимо построить остовное дерево (максимальное или минимальное) а исходя из него строить путь
кстати забыл уточнить, сложность задачи в наличии отрицательных рёбер

MBo (2007-07-26 08:44:00) [8]
http://algolist.ru/maths/graphs/index.php
и книги по графам

P.S. как "в ширину и в глубину" связано с мин. путями - не уловил :(

AZIZE (2007-07-25 16:56:00) [9]

> Игорь Шевченко © (25.07.07 16:50) [8]

не люблю людей которые из-за своего незнания ответа на вопрос пытаются выставить дураком кого-нибудь другого

Игорь Шевченко (2007-07-25 16:50:00) [10]
AZIZE © (25.07.07 16:37) [7]

Всесто того, отнимать у людей время на чтение вопросов, лучше воспользоваться поисковой системой. И информации больше и людей напряжешь меньше.

Читать до полного и окончательного просветления:
http://ln.com.ua/~openxs/articles/smart-questions-ru.html

AZIZE (2007-07-25 16:37:00) [11]

> не более умно, чем использовать сайт Delphimaster.ru вместо
> яндекса и гугля

использовал толку мало
а чем писатьь тупые ответы и отнимать у людей время на их прочтение лучше просто промолчать

AZIZE (2007-07-25 16:34:00) [12]

> можешь жадные алгоритмы поюзать

Это какие?

> орриентированный граф-то или нет?

нет

Игорь Шевченко (2007-07-25 16:34:00) [13]
AZIZE © (25.07.07 16:33) [4]

> очень умно

не более умно, чем использовать сайт Delphimaster.ru вместо яндекса и гугля.

AZIZE (2007-07-25 16:33:00) [14]

> Ищи в высоту и в толщину.

очень умно

Вася Правильный (2007-07-25 16:27:00) [15]
орриентированный граф-то или нет?

Вася Правильный (2007-07-25 16:26:00) [16]
можешь жадные алгоритмы поюзать

Игорь Шевченко (2007-07-25 16:21:00) [17]
Ищи в высоту и в толщину.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »