负权/圈有向循环图上的最短无圈路
我有一个有圈的有向图。所有边都是加权的，权重可以是负值。可能会有负循环。
共有1个答案
我将在CS理论StackExchange上复制我对这个问题的回答：
没有重复顶点的路径被称为简单路径，所以你要在一个负圈的图中寻找最短的简单路径。
这可以从最长路径问题中减少。如果你的问题有一个快速求解器，那么给出一个只有正边权的图，否定所有边权并运行你的求解器就会得到原始图中最长的路径。
因此你的问题是NP难的。
-
我试着用谷歌搜索，但是没有任何有价值的东西弹出。 图表： 它是无方向的 表示为具有双边的有向图 可能包含具有负权重的边 我知道我可以使用Bellman Ford在有向情况下解决这个问题，但是对于无向边，它只返回单边（2个循环）作为其输出。我需要找到一个循环的大小 此外，该算法应该具有运行时复杂性O（V*E）和内存复杂性O（V）。
-
我正在寻找一种算法，它可以<编码>不同两个有向无环图（DAG）。也就是说，我想要一个算法，它在第一个DAG上产生删除和插入序列，以产生第二个DAG。 我不是百分之百确定，但我认为一个最长的公共子序列可以应用于DAG。我不太关心结果编辑序列的长度（只要它足够短），更关心算法的运行时间。 一个复杂的问题是，除了一个根节点之外，没有一个顶点被标记。根节点也是唯一一个内边为零的节点。图的边被标记，图中的“
-
假设图G是一个有向无圈图，其顶点数为'n'no。如果我从图中移除所有边并使其完全断开，这会是一个DAG吗？
-
在一个已执行DFS的无向图中（为了生成一个DFS树，从而将每条边分类为树边或后边），图中是否存在仅由后边组成的循环，即没有树边？
-
给出了一个边上具有任意权的有向无环图和两个特定结点s和t，其中s的内度和t的外度为0。如何确定成本为正的s到t的最短路径？
-
我正在编写一个使用电网格分析的程序。所以我有电路的节点[A,B,C,D]和连接节点[0,1,2,3,4,5,6,7,8]的分支。 如何在具有多条边的无向图中找到最短的循环？ 图形图像（4个节点，9条边/分支）： 周期： 我需要的循环数是：循环=分支-（节点-1)，在本例中我需要6个循环。 我将这些数据存储在这样的数组中： 我很乐意看到任何语言的算法。