首页 文章

Dijkstra是DAG中最长的路径

提问于
浏览 次
10

我试图找出是否有可能使用Dijkstra算法找到有向非循环路径中的最长路径 . 我知道由于负成本周期，在一般图表中找不到Dijkstra的最长路径是不可能的 . 但我认为它应该在DAG中起作用 . 通过谷歌，我发现了许多相互矛盾的消息来源 . 有人说它在dag中工作，有些人说它不起作用，但我没有找到证明或反例 . 有人能指出我的证据或反例吗？

dijkstra longest-path

5 回答

  • 6

    我想到了这个问题，我认为一般来说这是不可能的 . 我想，存在非循环是不够的 .

    例如：

    我们想在这个dag中从a到c .

    a - > b - > c
|           /\
v           |
d - - - - -

    d-c的长度为4

    a-d的长度为1

    所有其他人的长度都是2

    如果只是用最大函数替换min函数，算法将导致a-b-c，但最长路径为a-d-c .

    我发现了两个特殊情况，您可以使用Dijkstra计算最长路径：

    • 图表不仅指向非循环，而且如果删除指示也是非循环的 . 换句话说：它是一棵树 . 因为在树中，最长路径也是最短路径 .

    • 图表只有负权重 . 然后你可以使用max而不是min来找到最长的路径 . 但这只适用于权重确实为负的情况 . 如果你只是反转正重量它将无法工作 .

    回复于
  • 2

    申请Dijkstra有三种可能的方式，其中没有一种可以使用：
    1.直接使用“max”操作而不是“min”操作 .
    2.将所有正权重转换为负数 . 然后找到最短的路径 .
    3.给出一个非常大的正数M.如果边的权重是w，那么现在用M-w代替w . 然后找到最短的路径 .

    对于DAG，关键路径方法将起作用：
    1：找到拓扑排序 .
    2：找到关键路径 .
    参见[Horowitz 1995] E. Howowitz，S . Sahni和D. Metha，C数据结构基础，计算机科学出版社，纽约，1995

    回复于
  • 0

    Longest distance problem has no optimal substructure 代表 any graph ，DAG与否 . 然而，图G上的任何最长距离问题等同于变换图G'中的最短距离问题G'= - G，即每个边权重的符号被反转 .

    如果变换后的图形G ' is expected to have negative edges and cycles, then Bellman-Ford algorithm is used for finding shortest distance. However, if G is guaranteed to have only non-negative weights (i.e. G'是非正权重，那么Dijkstra 's algorithm could be better choice over Bellman-Ford. (see ' Evgeny Kluev'对_498088的响应_）如果G是DAG，则G ' will be a DAG too. For DAG, we'更好的算法用于找到最短距离并且应该在Dijkstra 's or Bellman-Ford' s上选择 .

    Summary:
    最长的路径问题没有最优的子结构，因此修改Dijkstra中的最小权重函数可以用于图形，无论是否为DAG . 我们宁愿转换G，而不是修改任何最短路径算法（以微不足道的方式），并且看看哪个最短路径算法在转换后的G.上运行得最好 .

    Note

    A-------B
     |       |              assume: edges A-B, B-C, C-A of same weight
     |       |
     +-------C

    我们看到MAX_DIS（A，B）= A-> C-> B.
    对于"MAX_DIS"是最优结构，在上述情况下，是关系

    MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied.

    但它并不像我们所见，MAX_DIS（A，C）= A-> B-> C和MAX_DIS（C，B）= C-> A-> B因此它提供了一个最长距离问题可能没有的例子最佳子结构 .

    回复于
  • 0

    唯一的要求是不要有负循环 . 如果您没有周期，则可以通过将负权重中的最高绝对值添加到所有权重来重新映射负数 . 这样你就会失去负面的重量，因为所有的重量将等于或大于零 . 总而言之，唯一要担心的是没有负面循环 .

    回复于
  • 1

    我建议你修改Dijkstra算法来获取边权重的倒置值 . 由于图形是非循环的，因此算法不会进入无限循环，使用负权重来保持优化 . 更重要的是，现在正权重变为负数，但同样没有周期 . 即使图形是无向的，这也可以工作，前提是您不允许重新插入被访问的节点（即，停止两个节点之间的无限跳跃，因为添加负值总是会更好） .

    回复于

相关问题