На этом шаге продолжим рассматривать программную реализацию алгоритма Дейкстры.
Алгоритм Дейкстры можно представить следующей схемой (рис.1).
Рис.1. Схема алгоритма Дейкстры
node = find_ lowest_cost_node(costs) while node is not None: cost = costs[node] neighbors = graph[node] for n in neighbors.keys() : new_cost = cost + neighbors[n] if costs [n] > new_cost: cost s [n] = new_cost parents [n] = node processed. append (node) node = find_lowest_cost_node (costs) print(processed)
С функцией find_lowest_cost_node узел с наименьшей стоимостью находится так:
def find_lowest_cost_node(costs): lowest_cost = float("inf") lowest_cost_node = None for node in costs: cost = costs[node] if cost < lowest_cost and node not in processed: lowest_cost = cost lowest_cost_node = node return lowest_cost_node
Архив с примером можно взять здесь.
На следующем шаге проведем пошаговый анализ кода программы.
