Метод Дейкстры по поиску оптимального пути на графе

[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
Помогите разобраться, что же делать

[popolznev]

По-моему, вы всё правильно делаете, и никакого противоречия нет. Оптимальный путь не обязан быть виден на каждом шаге, он может вылезти в самом конце алгоритма.

И да, кстати, ведь путь через вершины 2 и 6 тоже оптимальный.

[TamaGOch]

popolznev, спасибо, разобрался, ведь действительно, если продолжать алгоритм, рассматривая вершины, достижимые из вершины 6 мы наткнёмся на вершину 7, у которой метка [3], предлагая ей метку [4], поэтому оставим [3] и путь через вершину 2 будет прекращён.
Просто смутил момент с тем, что в самом начале возникли две вершины минимальные, но если смотреть на это, как будто они обрабатываются параллельно, то всё нормально, ведь вершина 6 будет вершиной с минимальной меткой для верхнего пути, а вершина 7 будет вершиной с минимальной меткой для нижнего пути, как бы параллельно два пути смотрим.
Ладно, пример дорешаю, возможно, ещё с другим попробую и получится, спасибо!

[popolznev]

Да там не обязательно параллельно обрабатывать. Я как-то не вижу, в чём здесь может быть проблема. Можно обратить внимание разве на такой момент: в некоторых случаях у вас новое возможное значение метки для некоторой вершины совпадает со старым. И тогда у вас выбор: взять тот путь или этот, длины этих путей равны.