Есть список рёбер и список смежности вершин. Хочу написать алгоритм поиска кратчайших путей в графе. Дейкстры, Беллмана-Форда - без разницы. Но написать надо в функциональном стиле. Никак не могу это сделать, только в императивном могу. Может быть кто-то знает или есть готовые реализации? (python)
1 ответ
Взято из этого источника
def Dijkstra(N, S, matrix):
valid = [True]*N
weight = [1000000]*N
weight[S] = 0
for i in range(N):
min_weight = 1000001
ID_min_weight = -1
for j in range(N):
if valid[j] and weight[j] < min_weight:
min_weight = weight[j]
ID_min_weight = j
for z in range(N):
if weight[ID_min_weight] + matrix[ID_min_weight][z] < weight[z]:
weight[z] = weight[ID_min_weight] + matrix[ID_min_weight][z]
valid[ID_min_weight] = False
return weight
- N — количество вершин;
- S — номер стартовой вершины (отсчитывая от нуля);
- matrix — матрица смежности исходного графа, где несуществующие рёбра имеют бесконечный вес;
- В данном случае бесконечность равна 1000000;