Имеется некая карта с точками (вершины с координатами x,y)
Каждая вершина имеет набор связей c соседними вершинами (неориентированные ребра)
Имееются так же веса ребер... (ну, допустим, время перемещения)
Веса вершины нет.
Необходимо найти кратчайший путь из одной вершины в другую (с минимальным весом пути).
Подскажите, как это реализовать? ,буду рад любым ссылкам

Здравствуйте, Terre, Вы писали:

T>Имеется некая карта с точками (вершины с координатами x,y)
T>Каждая вершина имеет набор связей c соседними вершинами (неориентированные ребра)
T>Имееются так же веса ребер... (ну, допустим, время перемещения)
T>Веса вершины нет.
T>Необходимо найти кратчайший путь из одной вершины в другую (с минимальным весом пути).
T>Подскажите, как это реализовать? ,буду рад любым ссылкам

есть такай алгорит A*... в гугле поищи... по нему много инфы

Здравствуйте, AlexBar1, Вы писали:

AB>есть такай алгорит A*... в гугле поищи... по нему много инфы
Да, знаю, что есть
Поэтому и спрашиваю, чтоб не искать в гугле и не читать полностью теорию графов ))

Здравствуйте, AlexBar1, Вы писали:

AB>есть такай алгорит A*... в гугле поищи... по нему много инфы

Ну зачем так хардкорно? К нему надо ещё эвристику нормальную прикрутить (та, что используется в игрушках, не подходит). Человеку наверное хватит обычного алгоритма Дейкстры.

Здравствуйте, Terre, Вы писали:

AB>>есть такай алгорит A*... в гугле поищи... по нему много инфы
T>Да, знаю, что есть
T>Поэтому и спрашиваю, чтоб не искать в гугле и не читать полностью теорию графов ))

Э-э-э... А зачем всю-то теорию графов учить. Чтобы понять алгоритм, достаточно знать, что такое граф и с чем его едят.

Алгоритм Дейкстры может быть получен исходя из следующих соображений. Пусть у нас выделено некоторое множество A вершин графа, и пусть есть функция r(a), которая опрееляет предварительную оценку пути. Тогда обходим каждую выделенную вершину s и смотрим на все смежные с ней (e), при этом вычисляем путь r0 до e как r(s) + p(e), где p(s, e) — вес дуги из s в e. Если r0 оказалось меньше, чем r(e) или r(e) ещё не определено, то полагаем, что r(e) = r0 и выделяем e. Таким образом мы получаем новое множество A. Повторяем процесс, пока множество A не окажется пустым. Тогда r(a) будет содержать кратчайшее расстояние от начальной вершины до a. Изначально множество A должно содержать только начальную вершину s0, r(s0) = 0, а r(a) = inf (inf — бесконечность).

Здравствуйте, Terre, Вы писали:

T>Подскажите, как это реализовать? ,буду рад любым ссылкам

1. http://gzip.rsdn.ru/search/?group=15
2. http://www.google.ru/
3. http://gzip.rsdn.ru/forum/?mid=886770

Автор: Olegator
Дата: 05.11.04

и т.д.

Здравствуйте, Terre, Вы писали:

T>Имеется некая карта с точками (вершины с координатами x,y)
T>Каждая вершина имеет набор связей c соседними вершинами (неориентированные ребра)
T>Имееются так же веса ребер... (ну, допустим, время перемещения)
T>Веса вершины нет.
T>Необходимо найти кратчайший путь из одной вершины в другую (с минимальным весом пути).
T>Подскажите, как это реализовать? ,буду рад любым ссылкам

Если свое писать не хочется , есть много реализаций. В том числе есть boost graph library.

Здравствуйте, Terre, Вы писали:

T>Имеется некая карта с точками (вершины с координатами x,y)
T>Каждая вершина имеет набор связей c соседними вершинами (неориентированные ребра)
T>Имееются так же веса ребер... (ну, допустим, время перемещения)
T>Веса вершины нет.
T>Необходимо найти кратчайший путь из одной вершины в другую (с минимальным весом пути).
T>Подскажите, как это реализовать? ,буду рад любым ссылкам

В простейшем случае 5-строчного алгоритма Дейкстры хватит

X>В простейшем случае 5-строчного алгоритма Дейкстры хватит
В простейшем случае хватит и трёхстрочного алгоритма Флойда.

Здравствуйте, twisted_mind, Вы писали:

X>>В простейшем случае 5-строчного алгоритма Дейкстры хватит
_>В простейшем случае хватит и трёхстрочного алгоритма Флойда.
Это только если вершин с десяток. Иначе я бы сослался на алгоритмическую сложность ( O(N^2) vs O(N^3) )

X>Это только если вершин с десяток. Иначе я бы сослался на алгоритмическую сложность ( O(N^2) vs O(N^3) )

Про сложность я не спорю (правда, есть еще вариант реализации алгоритма Дейкстры со сложностью O(|V|log(|V|)) ). Просто если не очень критична производительность, человек совсем ничего не знает и некогда разбираться, то можно написать 3 строчки и забыть. А миллион простейший операций для 100 вершин — это не так уж много. При однократном запуске разницы с Дейкстрой на 100 вершинах на глаз вы вряд ли заметите.

Здравствуйте, twisted_mind, Вы писали:

_>правда, есть еще вариант реализации алгоритма Дейкстры со сложностью O(|V|log(|V|)
Нет такого варианта. По очевидным причинам.

_>>правда, есть еще вариант реализации алгоритма Дейкстры со сложностью O(|V|log(|V|)
А>Нет такого варианта. По очевидным причинам.

описАлся... я имел в виду |E|log(|E|)

Здравствуйте, twisted_mind, Вы писали:

_>описАлся... я имел в виду |E|log(|E|)

Скорее O(E*logV) или O(E+V*logV)

Здравствуйте, Vintik_69, Вы писали:

V_>Скорее O(E*logV) или O(E+V*logV)

При обычных предположениях (скажем, 2V < E < V^2), O(E log V) и O(E log E) -- это одно и то же

V_>Скорее O(E*logV) или O(E+V*logV)

Это всё понятно, но, как мне кажется, не имеет отношения к контексту разговора. Речь изначально шла об алгоритме Дейкстры "в пять строчек". Для O(E+V*logV) нужны фибоначчиевы кучи, что само по себе не пять строчек. А для O(E*logV) с помощью бинарной кучи нужна хотя бы процедура изменения приоритета элемента, чтобы в куче было всегда не более V элементов. Например, в C++ priority_queue и алгоритмы для кучи не имеют такой операции. В этом случае с priority_queue вообще всё плохо, а даже если пользоваться алгоритмами, эта операция — уже несколько строчек . Я имел в виду реализацию Дейкстры с бинарной кучей, когда вершина может быть занесена в кучу несколько раз, которая количеству кода, используя тот же priority_queue, ничем не отличается от варианта O(V^2) и даже немного удобнее в написании.