Код реализации алгоритма Йена

import networkx as nx
import heapq
import matplotlib.pyplot as plt
def yen_algorithm(graph, source, target, k):
    paths = []
    lengths = []
    candidates = []
    candidates_length = []
 
    #  алгоритм Дейкстры
    shortest_path = nx.shortest_path(graph, source=source, target=target, weight='weight')
    paths.append(shortest_path)
    lengths.append(nx.shortest_path_length(graph, source=source, target=target, weight='weight'))
 
    for i in range(1, k):
        for j in range(len(paths[i-1])-1):
            #итерация по вершинам предыдущего найденного пути
            spur_node = paths[i-1][j]#вершина, с которой будет будет начинаться новый путь
            root_path = paths[i-1][:j+1]#корневой путь
 
            for p in paths:
                #р-предыдущий путь, проверка между вершинами j и j+1 
                if root_path == p[:j+1] and graph.has_edge(p[j], p[j+1]):
                    graph.remove_edge(p[j], p[j+1])#удаление ребра
 
            try:
                spur_path = nx.shortest_path(graph, source=spur_node, target=target, weight='weight')
                total_path = root_path[:-1] + spur_path
                #
                if total_path not in candidates:
                    candidate_length = nx.shortest_path_length(graph, source=source, target=spur_node, weight='weight') + nx.shortest_path_length(graph, source=spur_node, target=target, weight='weight')
                    candidates.append(total_path)
                    candidates_length.append(candidate_length)
 
            except nx.NetworkXNoPath:
                continue
 
        if not candidates:
            break
 
        candidate_index = candidates_length.index(min(candidates_length))
        paths.append(candidates.pop(candidate_index))
        lengths.append(candidates_length.pop(candidate_index))
 
    return paths, lengths, candidates, candidates_length
 
# Пример использования
 
G = nx.Graph()
G.add_edge(1, 2, weight=30)
G.add_edge(1, 3, weight=30)
G.add_edge(1, 4, weight=20)
G.add_edge(2, 4, weight=70)
G.add_edge(2, 5, weight=50)
G.add_edge(3, 6, weight=60)
G.add_edge(4, 5, weight=40)
G.add_edge(4, 7, weight=80)
G.add_edge(5, 7, weight=50)
G.add_edge(5, 8, weight=90)
G.add_edge(6, 8, weight=50)
G.add_edge(7, 8, weight=20)
 
pos = nx.spring_layout(G)  # генерация позиций вершин
labels = nx.get_edge_attributes(G, 'weight')  # получение значений длин ребер
 
source = 1
target =8
k =3
 
result_paths, result_lengths, result_candidates, result_candidates_length = yen_algorithm(G, source, target, k)
 
nx.draw(G, pos, with_labels=True, node_size=600, node_color='lightcoral', font_weight='bold', font_size=10)
 
colors = ['orangered', 'gold', 'lime']  # Список цветов для каждого пути
 
for i, path in enumerate(result_paths):
    edges = list(zip(path, path[1:]))  # Получаем рёбра для каждого пути
    nx.draw(G, pos, edgelist=edges, edge_color=colors[i], width=3, with_labels=True, node_size=600, node_color='lightcoral', font_weight='bold', font_size=10)
 
plt.show()
 
print("Кратчайшие пути:", result_paths)
print("Длины кратчайших путей:", result_lengths)
print("Кандидаты:", result_candidates)
print("Длины кандидатов:", result_candidates_length)