Комментарии 31
Всегда интересно почитать очередной ликбез по какому-нибудь популярному алгоритму :)
вот здесь неплохие иллюстрации к алгоритму Дейкстры
Classic. Имхо, с этого алго начинается понимание графов.
не думаю что Дейкстра настолько сложный и необычный в реализации, чтобы использовать его в качестве статьи на хабре. Да и начинать надо было с dfs, bfs.
Еще есть такой вопрос, почему вы используете матрицу смежности, а не списки?
Вот из кода:
int MAX=0; //вместо бесконечности
почему ноль, когда у нас может быть ребро с весом ноль? бесконечность != 0. Нужен пример графа, когда алгоритм неверно сработает?
в проекте «Unit1.cpp» строки [50-61], не лень было ручками-то писать?
Еще есть такой вопрос, почему вы используете матрицу смежности, а не списки?
Вот из кода:
int MAX=0; //вместо бесконечности
почему ноль, когда у нас может быть ребро с весом ноль? бесконечность != 0. Нужен пример графа, когда алгоритм неверно сработает?
в проекте «Unit1.cpp» строки [50-61], не лень было ручками-то писать?
Написанию программы я уделил не так много времени, потому и код не идеален. А переменная int MAX в функции setMAX() меняется на сумму всех элементов матрицы умноженную на два.
имеем следующий орграф(список смежности)в виде (смежная вершина, вес ребра):
вершина 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, притом эта функция выполняется единожды по нажатию кнопки.(возможно не прав, код тяжелочитаемый).
А код должен быть не идеальным, а хотя бы правильным и читаемым, тем более вы предоставили его на публике.
вершина 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, притом эта функция выполняется единожды по нажатию кнопки.(возможно не прав, код тяжелочитаемый).
А код должен быть не идеальным, а хотя бы правильным и читаемым, тем более вы предоставили его на публике.
Согласен, даже в русской Википедии данный алгоритм описан достаточно подробно и очень понятно.
Спасибо, действительно все просто и понятно. Не умаляет статью и то, что сам алгоритм простой довольно.
Кстати, Дейкстра — это первый программист! Именно он написал это слово в качестве своей профессии в документах (точно не помню, кажется в свидетельстве о браке).
Кстати, Дейкстра — это первый программист! Именно он написал это слово в качестве своей профессии в документах (точно не помню, кажется в свидетельстве о браке).
> Этот граф мы можем представить в виде матрицы С:
И дальше повторяется исходный рисунок. Кажется, Вы что-то забыли :)
И дальше повторяется исходный рисунок. Кажется, Вы что-то забыли :)
дожились
На графике вес из 1 в 5 обозначен как 10, а в талице — 80. В обратном направлении — в таблице вообще не указан вес.
Можно было припомнить Флойда-Уоршалла и Форда-Беллмана, так как Дейкстра работает только для дуг из неотрицательными весами, а Флойд-Уоршалл — для всег весов и Форд-Беллман для релаксации…
Если я не ошибаюсь, то ошиблись вы:
Р = {1, 1, 5, 1, 5} -> {1,1,5,5,1}
Да вы, кажется, и сами об этом пишите:
«4-му элементу вектора Р значение W — P[4]=5»
Р = {1, 1, 5, 1, 5} -> {1,1,5,5,1}
Да вы, кажется, и сами об этом пишите:
«4-му элементу вектора Р значение W — P[4]=5»
1. А как, используя вектор P получить путь к вершине, если он проходит через 5 точек, а не через одну? Если я понял верно, то делать то же самое заново, но для этой предпоследней точки? както долго выглядит…
2. А почему «он будет некорректно работать если граф имеет дуги отрицательного веса.»?
2. А почему «он будет некорректно работать если граф имеет дуги отрицательного веса.»?
Это следует из аксиомы, на которую опирается данный алгоритм. Что при неотрицательных весах ребер кратчайший путь от одной вершины в другую смежную — прямой (с минимальной стоимостью за один шаг). Формулировка неточная, точную так сходу не вспомню. Но суть передал
Тот же вопрос имеется. Сейчас нужно написать такую же программу как в заголовке можно сказать. Пока решаю на бумажке, думаю над этим вектором 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. Это неправильно. Я что-то не так сделал? Вроде все как сказано здесь.
Вот матрица:
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. Это неправильно. Я что-то не так сделал? Вроде все как сказано здесь.
А мне нравятся такие неправильного вида крестики, нарисованные мышкой, которые показывают с какой любовью мы расстаемся с просмотренной вершиной :)
Ох как раз сегодня экзамен писал по Теории Телетрафика…
Спасибо Вам, испытал сладостное чувство ностальгии по своей исследовательскую работе в 10 классе.
Тогда я реализовывал и сравнивал различные алгоритмы поиска пути на графах, в итоге остановился на А* и подбирал для него хорошую эвристику на двумерной карте с движущимися препятствиями. К счастью, я потерял ее исходники в тот же год, и теперь я не умру от стыда, читая свой код.
Тогда я реализовывал и сравнивал различные алгоритмы поиска пути на графах, в итоге остановился на А* и подбирал для него хорошую эвристику на двумерной карте с движущимися препятствиями. К счастью, я потерял ее исходники в тот же год, и теперь я не умру от стыда, читая свой код.
А еще, для полноты картины, было бы неплохо рассказать почему алгоритм работает (и почему не работает при отрицательных весах).
Не то чтобы я хотел обидеть автора, но не вижу смысл в таких постах. Это либо проходит в университете на предмете «Алгоритмы и структуры данных» или в том же гугле и даже на хабре уже это всё расписано.
<зануда>
Ну и зачем в очередной раз разжевывать этот почти всем известный алгоритм?
Во всяком случае, это лучше чем писать посты о нвых айфонах.
</зануда>
Ну и зачем в очередной раз разжевывать этот почти всем известный алгоритм?
Во всяком случае, это лучше чем писать посты о нвых айфонах.
</зануда>
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе