Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе

[tkirill128]

Всегда интересно почитать очередной ликбез по какому-нибудь популярному алгоритму :)

[rusy]

вот здесь неплохие иллюстрации к алгоритму Дейкстры

[BlastBeat]

Classic. Имхо, с этого алго начинается понимание графов.

[XaosSintez]

есть алгоритмы на графы и чуть попроще. Поиск в глубину\ширину например. Лично я с них начинал :)

[BlastBeat]

Согласен, но поиски базовые и очевидные, а с этого начинаются изящества графов)

[Laytlas]

А, что же вы делаете! Нельзя забывать о табуляции, иначе получается быдло-код.
Алгоритм флойда записывается в 3 строчки! (во всяком случае его основная суть)

[burdakovd]

тогда уже в четыре: три оператора цикла + строчка собственно кода
Это если не считать строчки с операторными скобками

[mihaildemidoff]

не думаю что Дейкстра настолько сложный и необычный в реализации, чтобы использовать его в качестве статьи на хабре. Да и начинать надо было с dfs, bfs.
Еще есть такой вопрос, почему вы используете матрицу смежности, а не списки?
Вот из кода:
int MAX=0; //вместо бесконечности
почему ноль, когда у нас может быть ребро с весом ноль? бесконечность != 0. Нужен пример графа, когда алгоритм неверно сработает?
в проекте «Unit1.cpp» строки [50-61], не лень было ручками-то писать?

[splitface]

Написанию программы я уделил не так много времени, потому и код не идеален. А переменная int MAX в функции setMAX() меняется на сумму всех элементов матрицы умноженную на два.

[mihaildemidoff]

имеем следующий орграф(список смежности)в виде (смежная вершина, вес ребра):
вершина 1) (2,0) (3,6)
вершина 2) (4,5)
вершина 3) (4,7)
вершина 4) (5,8)
Ваша программа говорит нам о следующем:
Кратчайшие маршруты:
1 -> 3 = 6
1 -> 3 -> 4 = 13
1 -> 3 -> 4 -> 5 = 21
и это всё.
а ваша функция делает лишний N*N, притом эта функция выполняется единожды по нажатию кнопки.(возможно не прав, код тяжелочитаемый).
А код должен быть не идеальным, а хотя бы правильным и читаемым, тем более вы предоставили его на публике.

[Intilt]

Согласен, даже в русской Википедии данный алгоритм описан достаточно подробно и очень понятно.

[Monca]

Спасибо, действительно все просто и понятно. Не умаляет статью и то, что сам алгоритм простой довольно.
Кстати, Дейкстра — это первый программист! Именно он написал это слово в качестве своей профессии в документах (точно не помню, кажется в свидетельстве о браке).

[Hexenlord]

> Этот граф мы можем представить в виде матрицы С:

И дальше повторяется исходный рисунок. Кажется, Вы что-то забыли :)

[splitface]

Спасибо. Исправил.

[Wildy]

дожились

[smartly]

На графике вес из 1 в 5 обозначен как 10, а в талице — 80. В обратном направлении — в таблице вообще не указан вес.

[Latobco]

Можно было припомнить Флойда-Уоршалла и Форда-Беллмана, так как Дейкстра работает только для дуг из неотрицательными весами, а Флойд-Уоршалл — для всег весов и Форд-Беллман для релаксации…

[iambot]

Если я не ошибаюсь, то ошиблись вы:
Р = {1, 1, 5, 1, 5} -> {1,1,5,5,1}
Да вы, кажется, и сами об этом пишите:
«4-му элементу вектора Р значение W — P[4]=5»

[iPavel]

1. А как, используя вектор P получить путь к вершине, если он проходит через 5 точек, а не через одну? Если я понял верно, то делать то же самое заново, но для этой предпоследней точки? както долго выглядит…
2. А почему «он будет некорректно работать если граф имеет дуги отрицательного веса.»?

[XaosSintez]

Это следует из аксиомы, на которую опирается данный алгоритм. Что при неотрицательных весах ребер кратчайший путь от одной вершины в другую смежную — прямой (с минимальной стоимостью за один шаг). Формулировка неточная, точную так сходу не вспомню. Но суть передал

[vladsharikov]

Тот же вопрос имеется. Сейчас нужно написать такую же программу как в заголовке можно сказать. Пока решаю на бумажке, думаю над этим вектором P.

Вот матрица:
0 3 0 0 7 0 0 0 0
3 0 4 9 0 0 0 0 0
0 4 0 0 0 2 8 0 0
0 9 0 0 0 7 0 0 4
7 0 0 0 0 0 1 0 0
0 0 2 7 0 0 1 7 0
0 0 8 0 1 1 0 2 0
0 0 0 0 0 7 2 0 0
0 0 0 4 0 0 0 0 0

Или граф:


Наикратчайший маршрут из 7 из 9 такой: 7->6->4->9. Делая как предлагает автор, я получил вектор P = {1,1,6,1,1,1,1,1,4}. Из этого следует, что в 3 вершину путь такой: 7 -> 6 -> 3 — правильно. Но в 9 такой: 7 -> 4 -> 9. Это неправильно. Я что-то не так сделал? Вроде все как сказано здесь.

[sige]

А мне нравятся такие неправильного вида крестики, нарисованные мышкой, которые показывают с какой любовью мы расстаемся с просмотренной вершиной :)

[und]

Ох как раз сегодня экзамен писал по Теории Телетрафика…

[ntkt]

Спасибо Вам, испытал сладостное чувство ностальгии по своей исследовательскую работе в 10 классе.
Тогда я реализовывал и сравнивал различные алгоритмы поиска пути на графах, в итоге остановился на А* и подбирал для него хорошую эвристику на двумерной карте с движущимися препятствиями. К счастью, я потерял ее исходники в тот же год, и теперь я не умру от стыда, читая свой код.

[susl]

А еще, для полноты картины, было бы неплохо рассказать почему алгоритм работает (и почему не работает при отрицательных весах).

[goodman]

Не то чтобы я хотел обидеть автора, но не вижу смысл в таких постах. Это либо проходит в университете на предмете «Алгоритмы и структуры данных» или в том же гугле и даже на хабре уже это всё расписано.

[dslf]

<зануда>
Ну и зачем в очередной раз разжевывать этот почти всем известный алгоритм?
Во всяком случае, это лучше чем писать посты о нвых айфонах.
</зануда>

[goodman]

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