python-Igraph / networkx中的k最短路径实现(日元算法)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python-Igraph / networkx中的k最短路径实现(日元算法)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3803字，纯文字阅读大概需要6分钟。

内容图文

经过深入研究并基于this,this等,我建议实现k最短路径算法,以便在大型无向,循环加权图中找到第一,第二,第三…第k个最短路径.大约2000个节点.

Wikipedia上的伪代码是这样的：

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.

附言可能没有其他可行的解决方法,因为我们已经在这里进行了研究.我已经收到很多建议,而且我对社区有很多欠. DFS或BFS无法正常工作.图是巨大的.

编辑：我一直在纠正python脚本.简而言之,这个问题的目的是正确的脚本.

解决方法:

在Github,YenKSP上有一个Yen’s KSP的python实现.完全感谢作者,此处给出了算法的核心：

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

内容总结

以上是互联网集市为您收集整理的python-Igraph / networkx中的k最短路径实现(日元算法)全部内容，希望文章能够帮你解决python-Igraph / networkx中的k最短路径实现(日元算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---