реализация k кратчайших путей в Igraph / networkx (алгоритм Йена)

После тщательного исследования и на основе этого, это и многое другое. Мне было предложено реализовать алгоритм k кратчайших путей, чтобы найти первый, второй, третий ... k-й кратчайший путь в большом неориентированный, циклический, взвешенный граф. Около 2000 узлов.

Псевдокод в Википедии следующий:

function YenKSP(Graph, source, sink, K):
  //Determine the shortest path from the source to the sink.
 A[0] = Dijkstra(Graph, source, sink);
 // Initialize the heap to store the potential kth shortest path.
 B = [];

for k from 1 to K:
   // The spur node ranges from the first node to the next to last node in the shortest path.
   for i from 0 to size(A[i]) − 1:

       // Spur node is retrieved from the previous k-shortest path, k − 1.
       spurNode = A[k-1].node(i);
       // The sequence of nodes from the source to the spur node of the previous k-shortest path.
       rootPath = A[k-1].nodes(0, i);

       for each path p in A:
           if rootPath == p.nodes(0, i):
               // Remove the links that are part of the previous shortest paths which share the same root path.
               remove p.edge(i, i) from Graph;

       // Calculate the spur path from the spur node to the sink.
       spurPath = Dijkstra(Graph, spurNode, sink);

       // Entire path is made up of the root path and spur path.
       totalPath = rootPath + spurPath;
       // Add the potential k-shortest path to the heap.
       B.append(totalPath);

       // Add back the edges that were removed from the graph.
       restore edges to Graph;

   // Sort the potential k-shortest paths by cost.
   B.sort();
   // Add the lowest cost path becomes the k-shortest path.
   A[k] = B[0];
return A;

Основная проблема в том, что я еще не мог написать правильный скрипт на Python для этого (удалить края и правильно установить их на место), поэтому я дошел до этого только с использованием Igraph, как обычно:

def yenksp(graph,source,sink, k):
    global distance
    """Determine the shortest path from the source to the sink."""
    a = graph.get_shortest_paths(source, sink, weights=distance, mode=ALL, output="vpath")[0]
    b = [] #Initialize the heap to store the potential kth shortest path
    #for xk in range(1,k):
    for xk in range(1,k+1):
        #for i in range(0,len(a)-1):
        for i in range(0,len(a)):
            if i != len(a[:-1])-1:
                spurnode = a[i]
                rootpath = a[0:i]
                #I should remove edges part of the previous shortest paths, but...:
                for p in a:
                    if rootpath == p:
                        graph.delete_edges(i) 

            spurpath = graph.get_shortest_paths(spurnode, sink, weights=distance, mode=ALL, output="vpath")[0]
            totalpath = rootpath + spurpath
            b.append(totalpath)
            # should restore the edges
            # graph.add_edges([(0,i)]) <- this is definitely not correct.
            graph.add_edges(i)
        b.sort()
        a[k] = b[0]
    return a

Это действительно плохая попытка, и она возвращает только список в списке

Я уже не очень уверен, что делаю, и я уже очень отчаялся с этой проблемой, и в последние дни моя точка зрения на это была изменена на 180 градусов и даже один раз. Я просто новичок, старающийся изо всех сил. Пожалуйста помоги. Также можно предложить реализацию Networkx.

P.S. Скорее всего, нет других рабочих способов по этому поводу, потому что мы уже исследовали это здесь. Я уже получил много предложений и многим обязан сообществу. DFS или BFS не работают. График огромен.

Изменить: я продолжаю исправлять скрипт Python. Короче говоря, цель этого вопроса - правильный сценарий.