АЛГОРИТМ ЙЕНА PYTHON

Алгоритм Йена (Yen's algorithm) - это алгоритм поиска кратчайшего пути в графе с помощью обхода К-кратчайших путей. Данный алгоритм был разработан Шу Яном (Shu Yan) и был опубликован в 1971 году Чином Ли Йеном (Chin-Ning Lee Yen). Алгоритм Йена удобен для использования в задачах маршрутизации сетей связи и транспортных систем.

Реализация алгоритма Йена на языке Python является относительно простой задачей. Приведем пример кода, который строит граф и выполняет поиск трех кратчайших путей между двумя вершинами:

import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('B', 'C', weight=8)
G.add_edge('C', 'D', weight=7)
G.add_edge('D', 'E', weight=9)
G.add_edge('E', 'F', weight=10)
G.add_edge('F', 'G', weight=2)
G.add_edge('G', 'H', weight=1)
G.add_edge('H', 'E', weight=5)
paths = list(nx.shortest_simple_paths(G, 'A', 'H', weight='weight'))
for i in range(3):
print(paths[i])

В результате выполнения данного кода будут выведены три кратчайших пути между вершинами A и H.