На этом шаге продолжим рассматривать программную реализацию алгоритма Дейкстры.

    Также понадобится хеш-таблица для хранения стоимостей всех узлов (рис.1).

Рис.1. Хеш-таблица стоимостей узлов

    Стоимость узла определяет, сколько времени потребуется для перехода к этому узлу от начального узла. Вы знаете, что переход от начального узла к узлу В занимает 2 минуты. Вы знаете, что для перехода к узлу А требуется 6 минут (хотя, возможно, вы найдете более быстрый путь). Вы не знаете, сколько времени потребуется для достижения конечного узла. Если стоимость еще неизвестна, она считается бесконечной. Как представить бесконечность в PytЬon?

infinity = float("inf")

    Код создания таблицы стоимостей costs:

costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

    Для родителей также создается отдельная таблица (рис.2):

Рис.2. Хеш-таблица родителей

    Код создания хеш-таблицы родителей:

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

    Наконец, вам нужен массив для отслеживания всех уже обработанных узлов, так как один узел не должен обрабатываться многократно:

processed = []

    На этом подготовка завершается. Теперь обратимся к алгоритму.

    На следующем шаге рассмотрим реализацию алгоритма Дейкстры.

Предыдущий шаг Содержание Следующий шаг