DAG中最长的路径

3 回答

• 2

  您的第二个选项不正确：DFS不会探索所有可能的路径，除非您的图形是树或森林，并且您从根开始 . 我知道的第二个算法是否定权重并找到最短路径，但它比你列为＃1的top sort + DP algorithm慢一些 .

  回复于 2024-04-29T13:22:47+08:00
• 8

  使用“DFS”枚举DAG中的所有路径：

  def enumerate_dag(g):
  
    def enumerate_r(n, paths, visited, a_path = []):
      a_path += [n]
      visited[n] = 1
      if not g[n]:
          paths += [list(a_path)]
      else:
          for nn in g[n]:
              enumerate_r(nn, paths, visited, list(a_path))
  
    paths, N = [], len(g)
    visited = np.zeros((N), dtype='int32')
  
    for root in range(N):
      if visited[root]: continue
      enumerate_r(root, paths, visited, [])
  
    return paths
  

  回复于 2024-04-29T13:22:47+08:00
• 3

  不需要DFS . 算法：采用DAG G.每个弧保存一个变量E.

  for each node with no predecessor :
      for each of his leaving arcs, E=1.
  for each node whose predecessors have all been visited :
      for each of his leaving arcs, E=max(E(entering arcs))+1.
  

  max_path是处理完所有节点后边缘内的最高E.

  回复于 2024-04-29T13:22:47+08:00