Форум: "Начинающим";
Текущий архив: 2007.08.19;
Скачать: [xml.tar.bz2];
ВнизПоиск в графе Найти похожие ветки
← →
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]
> сложность задачи в наличии отрицательных рёбер
весов? и чего там сложного?
или все-таки направлений?
← →
MBo © (2007-07-26 10:50) [14]>весов? и чего там сложного?
Ну например, алг. Дейкстры для отриц. весов непригоден, а Флойда - работает (правда, он для всех пар вершин сразу)
← →
Вася Правильный (2007-07-26 11:13) [15]
> алг. Дейкстры для отриц. весов непригоден
это легко обходится плюсованием ко всем весам константы так, чтоб минимальный был 0
← →
AZIZE © (2007-07-26 11:32) [16]
> это легко обходится плюсованием ко всем весам константы
> так, чтоб минимальный был 0
данный вариант нериемлем, т. к. в случае поика минимума необходимо найти действительно минимальный вес (отрицательный)
да и ещё одно условие все веса лежат в диапазоне [-1..1]
← →
MBo © (2007-07-26 11:40) [17]>это легко обходится плюсованием ко всем весам константы так, чтоб минимальный был 0
Ну прямо так просто? Контрпример:
A-B 5
A-C 2
C-D -1
D-B 3
кратчайший путь из A в B - A_C_D_B
а если добавить ко всем весам 1, чтобы занулить СD, то Дейкстра получит "левый" кратчайший путь A_B
Конечно, есть модификации Дейкстры (например, с потенциалами), решающие проблему отриц. весов, тем не менее она существует...
Страницы: 1 вся ветка
Форум: "Начинающим";
Текущий архив: 2007.08.19;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.042 c