Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Начинающим";
Текущий архив: 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
15-1185232100
Kostafey
2007-07-24 03:08
2007.08.19
С днем рождения ! 24 июля


4-1172557563
GrayFace
2007-02-27 09:26
2007.08.19
"Сбросить" ListView_SetColumnWidth при ViewStyle = vsList


15-1184687428
Ricks
2007-07-17 19:50
2007.08.19
Обман программы


3-1178281496
alsov
2007-05-04 16:24
2007.08.19
ADO+ftCursor+Oracle


2-1185025167
CatAlone
2007-07-21 17:39
2007.08.19
Drag and drop и extractfilename





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский