Поиск в графе

← →
AZIZE © (2007-07-25 16:12) [0]

Люди! нужно максимум различных способов нахождения максимального и минимального пути в графе от вершины А к вершине В;
В случае максимального, исключать циклический поиск;
Методы Краскала, Прима, в ширину и в глубину можно не предлагать они уже реализованы
заранее спасибо

← →
Игорь Шевченко © (2007-07-25 16:21) [1]

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

← →
Вася Правильный (2007-07-25 16:26) [2]

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

← →
Вася Правильный (2007-07-25 16:27) [3]

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

← →
AZIZE © (2007-07-25 16:33) [4]

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

очень умно

← →
Игорь Шевченко © (2007-07-25 16:34) [5]

AZIZE © (25.07.07 16:33) [4]

> очень умно

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

← →
AZIZE © (2007-07-25 16:34) [6]

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

Это какие?

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

нет

← →
AZIZE © (2007-07-25 16:37) [7]

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

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

← →
Игорь Шевченко © (2007-07-25 16:50) [8]

AZIZE © (25.07.07 16:37) [7]

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

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

← →
AZIZE © (2007-07-25 16:56) [9]

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

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

← →
MBo © (2007-07-26 08:44) [10]

http://algolist.ru/maths/graphs/index.php
и книги по графам

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

← →
AZIZE © (2007-07-26 09:54) [11]

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

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

← →
AZIZE © (2007-07-26 09:56) [12]

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

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

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

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

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

>весов? и чего там сложного?
Ну например, алг. Дейкстры для отриц. весов непригоден, а Флойда - работает (правда, он для всех пар вершин сразу)

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

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

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

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

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

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

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

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

Поиск в графе Найти похожие ветки