@TamaGOch

По курсу методов оптимизации возникла задача в решении примера поиска оптимального пути на графе с применением метода Дейкстры. Чтобы продемонстрировать, насколько этот метод не получается понять, прилагаю сам граф и попытку решения. Граф ориентированный, со скалярными весами рёбер. Как рисовать граф в latex не знаю, поэтому таблицей. В нулевом столбце - вершины "откуда", в нулевой строке - вершины "куда", на пересечении - затраты.

xx 1 2 3 4 5 6 7 8 9 10
______________________
01|..1.......3.....1...
02|....2.....1.........
03|......4.............
04|........2.....1.....
05|....................
06|............2...1...
07|......2.............
08|........1...........
09|............2......6
10|............4.8.....
Стартовая вершина - 1(первая), финальная - 5(пятая)
шаг 0: вершина 1 получает метку [0], остальные [бесконечность]
шаг 1: рассматриваем вершины, достижимые из вершины 1, это вершины 2, 6 и 9, метки переписываются следующим образом:
1 [0]
2 [1]
3 [бесконечность]
4 [бесконечность]
5 [бесконечность]
6 [3]
7 [бесконечность]
8 [бесконечность]
9 [1]
10 [бесконечность]

шаг 2: далее, как следует из википедии и из методички нашей, следует рассматривать ближайшую вершину к вершине 1, в данном случае у меня их две: это вершины 2 и 9, что же, попробую рассмотреть их обе.
для вершины 2 достижимыми являются вершины 3 и 6. Значение метки для вершины 6 меняется с [3] на [2], ибо меньше, для вершины 3 всё как обычно, [бесконечность] на [3]. Итого:
1 [0]
2 [1]
3 [3] (new)
4 [бесконечность]
5 [бесконечность]
6 [2] (new)
7 [бесконечность]
8 [бесконечность]
9 [1]
10 [бесконечность]
А также рассматриваем вершину 9. Из неё достижимы вершины 7 и 10, здесь так:
1 [0]
2 [1]
3 [3] (new)
4 [бесконечность]
5 [бесконечность]
6 [2] (new)
7 [3] (new)
8 [бесконечность]
9 [1]
10 [7] (new)
что делать дальше, не знаю. По сути, новые метки появились у вершин 3, 6, 7, 10. И надо выбрать из них наименьшую, и то будет вершина 6, но уже тут отклонимся от оптимального пути, так как оптимальный путь 1-9-7-4-5
Помогите разобраться, что же делать

0

@TamaGOch

Наврал, вот граф))
Красным - номер вершины, синим - затраты на переход по ребру

Миниатюры

 

0

@ilotan

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



Ставим ноль той веришне, из которой будем искать пути до других вершин, штрихуем тк от самой до себя крачайшее расстояние 0.(первая строка)

Во второй строке смотрим по графу (или матрице) переписываем известные нам веса инцидентных ребер тех вершин, до которых мы знаем как дойти(2, 6, 9) и в качестве метки берем минимальное расст. ( |<x(s), 2>| - единица), штрихуем.

В третьей строке : из второй вершины мы знаем как дойти до 3, 6, 9. смотрим по матрице из 2 в 3 вес ребра - 2, прибавляем к единичке и смотрим меньше ли тройка бесконечности? если меньше переписываем, если больше оставляем бесконечность. также для 6 и 9 вершины.

В 4 строке: в качестве метки выбрали 9 вершину кр. расст из x(s) - единица. делаем все тоже самое. если сумма единицы(метки) и веса ребра из матрицы больше, предыдущего то мы сносим предыдущую метку, иначе пишем новую.

Прокомментирую еще 7 строку.

в 7 строке: в качестве метки выбрали 7 вершину с кр. расст. из x(s) - 3. из 7 вершины в 4 по матрице вес ребра - 2, прибавляем к тройке двойку получаем - 5, 5<7? да. переписываем пятёрку, которую в последующем и выберем в качестве очередной метки.
и так далее до конца.



получили кратчайший путь из x(s) в x(t): x(s) - 9 - 7 - 4 - x(t)
кратчайшее расстояние из x(s) в x(t) : 7.



Если будут вопросы, спрашивайте)

0

@AdmiralHood

Как видите, два кратчайших пути.
В квадратиках - минимальное расстояние от вершины 1 до данной вершины

0

@ilotan

да, еще 1 забыл

0