Застрял в алгоритме Джикстра

Question

Я пытаюсь применить алгоритм Джикстры к этому графику из моего учебника, но я продолжаю застрять в вершине A при попытке перейти из G-> C.Вот ссылка на изображение графика: ССЫЛКА

Я опишу мои шаги ниже:

1. Я начинаюв начальной вершине (G).

2. A получает стоимость 6, E получает стоимость 1, H получает стоимость 4, поскольку все они изначально бесконечны.G отмечен как посещенный.

3. Я иду к соседу с наименьшей стоимостью;в этом случае его E.

4. В E я устанавливаю стоимость B как 1 + 2 = 3, а стоимость F как 1 + 2 = 3. Затем отмечается Eкак посещено.

5. Я посещаю соседа E с наименьшей стоимостью: Здесь я начинаю застрять, так как и B, и F имеют одинаковую стоимость. Предположим, что явыберите B.
6. В B я устанавливаю стоимость C как 3 + 7 = 10, а стоимость A - 5.
7. Теперь A - сосед с наименьшей стоимостью, но доступ к нейзаставляет меня застрять, так как я не могу выйти.

Я был бы очень признателен за некоторые предложения или исправления, если я подхожу к этому неправильно.

Answer 1

На шаге 6 посещенные узлы - это G, E и B. Теперь вам нужно выбрать узел с минимальным значением расстояния , которое равно F. Так что недостаток на шаге 7 действительнопредположение, что это должен быть соседний узел.

Продолжая с шага 7:

Выбор F. Обновление расстояния С до 6. Отметьте посещение F. Выбор H. Обновление расстояния D до 6. Отметьте посещение Н. Теперь выберите А. Обновления не требуются.Отметьте посещенных. Выберите C или D в любом порядке и отметьте их как посещенных.Обновления здесь не требуются.

Answer 2

Поскольку G уже помечен как посещенный, этот узел больше не рассматривается, и, следовательно, A также рассматривается, поскольку больше нет возможных соединений.