k implémentation des chemins les plus courts dans Igraph/networkx (algorithme de Yen)

Question

Après une recherche approfondie et basée sur this, this et beaucoup plus, j'ai été suggéré d'implémenter k algorithme de chemins les plus courts afin de trouver premier, deuxième, troisième ... -le plus court chemin dans un grand graphe non cyclique, pondéré et non orienté. Environ 2000 nœuds.

Le pseudo-code sur Wikipedia est la suivante:

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; 

Le principal problème est que je ne pouvais pas écrire le script python correct pour ce (supprimer les bords et les place en place correctement) donc j'ai seulement obtenu loin avec reliyng sur iGRAPH comme d'habitude:

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 

il est d'essayer vraiment pauvre et il retourne une seule liste dans une liste

Je ne suis pas ver Je suis sûr de ce que je fais et je suis très désespéré avec cette question et dans les derniers jours, mon point de vue sur ce point a été changé à 180 degrés et même une fois. Je suis juste un noob qui fait de son mieux. S'il vous plaît aider. La mise en œuvre de Networkx peut également être suggérée.

P.S. Il est probable qu'il n'y a pas d'autres façons de travailler à ce sujet parce que nous avons déjà fait des recherches ici. J'ai déjà reçu beaucoup de suggestions et je dois beaucoup à la communauté. DFS ou BFS ne fonctionnera pas. Le graphique est énorme. Edit: Je continue à corriger le script python. En un mot, le but de cette question est le bon script.

Answer 1

Il existe une implémentation python de KSP de Yen sur Github, YenKSP. Donner plein crédit à l'auteur, au cœur de l'algorithme est donnée ici:

def ksp_yen(graph, node_start, node_end, max_k=2): 
    distances, previous = dijkstra(graph, node_start) 

    A = [{'cost': distances[node_end], 
      'path': path(previous, node_start, node_end)}] 
    B = [] 

    if not A[0]['path']: return A 

    for k in range(1, max_k): 
     for i in range(0, len(A[-1]['path']) - 1): 
      node_spur = A[-1]['path'][i] 
      path_root = A[-1]['path'][:i+1] 

      edges_removed = [] 
      for path_k in A: 
       curr_path = path_k['path'] 
       if len(curr_path) > i and path_root == curr_path[:i+1]: 
        cost = graph.remove_edge(curr_path[i], curr_path[i+1]) 
        if cost == -1: 
         continue 
        edges_removed.append([curr_path[i], curr_path[i+1], cost]) 

      path_spur = dijkstra(graph, node_spur, node_end) 

      if path_spur['path']: 
       path_total = path_root[:-1] + path_spur['path'] 
       dist_total = distances[node_spur] + path_spur['cost'] 
       potential_k = {'cost': dist_total, 'path': path_total} 

       if not (potential_k in B): 
        B.append(potential_k) 

      for edge in edges_removed: 
       graph.add_edge(edge[0], edge[1], edge[2]) 

     if len(B): 
      B = sorted(B, key=itemgetter('cost')) 
      A.append(B[0]) 
      B.pop(0) 
     else: 
      break 

    return A 

Answer 2

J'ai eu le même problème que vous, donc je Ported de pseudo-code de Wikipedia pour l'algorithme de Yen pour une utilisation en Python avec la bibliothèque igraph.

Vous pouvez y trouver: https://gist.github.com/ALenfant/5491853