-
10 votesanswersviews
Dijkstra是DAG中最长的路径
我试图找出是否有可能使用Dijkstra算法找到有向非循环路径中的最长路径 . 我知道由于负成本周期,在一般图表中找不到Dijkstra的最长路径是不可能的 . 但我认为它应该在DAG中起作用 . 通过谷歌,我发现了许多相互矛盾的消息来源 . 有人说它在dag中工作,有些人说它不起作用,但我没有找到证明或反例 . 有人能指出我的证据或反例吗? -
2 votesanswersviews
如何从固定节点开始获取DAG中最长的路径?
我想知道如何从节点0(最小节点)开始在DAG中获取最长路径 我搜索了wiki并得到了以下算法: algorithm dag-longest-path is input: Directed acyclic graph G output: Length of the longest path length_to = array with |V(G)| elements of ... -
1 votesanswersviews
使用Python中的Networkx在DAG上查找最长路径
我有一个非常大的字符串DAG(~200k) . 我想找到此图中存在的最长路径 . 下面的代码是我如何设置图表(从字符串列表 new_list ) . #create new empty graph g = nx.DiGraph() #add all words to graph for word in new_list: g.add_node(word) #fill graph wit... -
1 votesanswersviews
使用Python中的Networkx从DAG中找到最长的加权路径?
我需要一个算法来找到有向非循环图中最长的加权路径 networkx.MultiDiGraph() . 我的图形具有加权边缘,并且许多边缘具有空值作为加权 . 在networkx doc中,我找不到解决这个问题的方法 . 我的图表具有以下结构: >>> print graph.nodes() [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, ... -
-1 votesanswersviews
NetworkX在开始顶点找到DAG中最长路径而没有错误的最有效方法
从某个顶点开始,如何找到相对于该顶点的最长路径?我一直在浏览,无法找到这个问题的解决方案,这个问题实际上适用于所有可能的DAG案例 . NetworkX中的源代码是首选,但常规的python也很好 . 我真的很好奇为什么我无法找到任何正确的工作示例,我确实理解这是一个NP型问题,但我想知道它最有效的方式 . -
2 votesanswersviews
NetworkX:在DAG中查找最长路径,返回所有关联最大值
我无法弄清楚如何更新networkx dag_find_longest_path()算法以返回绑定“N”而不是返回找到的第一个最大边缘,或者返回所有与最大权重相关的边缘列表 . 我首先从pandas dataframe创建了一个DAG,它包含一个像下列子集一样的边缘列表: edge1 edge2 weight 115252161:T 115252162:A ...