15

我想知道，当无向图中有多个直接连接时，Dijkstra 的算法是否能正常工作。

例如：

在此处输入图像描述

我想使用 Dijkstra 来找到最快的路径，但是还有一个附加条件。边缘上所有附加数据的总和不能> = x。所以，如果它出现了带有 weight: 3 的边缘，使用错误，我的程序将尝试使用第二个边缘。

additional_data编辑：我的任务是在边缘的总和不能高于 x的附加条件下找到最快的路径。你能告诉我如何处理这个问题吗？

编辑2：（设置赏金）

在找到此链接之前，我一直在研究互联网。有一个关于如何做我要求的事情的解释。（中上头）

我现在正在尝试以某种方式使用它 2 天，但我担心我不能正确理解这个算法。我想请你们中的一些人帮助我解决这个问题，通过更多的例子来解释我（几个第一步）。这是示例：

在此处输入图像描述

4

8 回答 8

8

我认为您可以修改 Dijkstra 的算法来处理这个问题。Dijkstra 的算法基本上是通过逐步构建一个表来列出到每个节点的最短路径来工作的。相反，您将构建一个表格，列出在给定成本下到每个节点的最短路径。或者更确切地说，在给定的成本或更少，即在给定的预算。

更正式地说，您可以将原始图转换为另一个图，然后将 Dijkstra 应用于该图。假设 additional_data 成本始终是整数，则转换为：

  1. 取每个原始节点 n 并为从 0 到预算值的每个整数值 c 创建一组节点 (n, c)（您可以容忍的最大附加数据总和）
  2. 取每个原始连接 n1 -> n2，权重为 w，additional_data a，并创建一组从每个节点 (n1, c) 到节点 (n2, c+a) 的连接，每个连接的权重为 w

原始图模型中的节点在空间中的位置。转换后的图模型中的节点位于状态空间中，其中状态变量是位置，以及到目前为止花费的预算金额。

如果您想以 x 的预算从 A 到 Z，那么您只需使用 Dijkstra 算法找到从 (A, 0) 到其中一个节点 (Z, c <= x) 的路线。

编辑：我已经实现了修改后的 Dijkstra 算法：https ://bitbucket.org/twic/roadsproblem 。它的症结在于src/solver.py。

于 2013-01-06T18:02:26.383 回答
5

这是您找到的算法如何处理示例问题的说明。

问题是在沿途累积成本不应超过 的额外条件下，找到两者node one之间的最短路径。node four7

我们想要找到的解决方案是首先从node one到节点node two，距离为190，成本为4。然后从node two使用node four距离195和成本的路径出发3。总而言之，路径的距离为385，成本为7。

步骤1

那么算法是如何找到这个的呢？第一步是minArray(i,j)像您所做的那样设置矩阵。数组的元素(i,j)包含您必须经过的距离才能到达节点j，并且正好有i剩余的钱。

原始数组。

一开始没有访问过的元素，因为我们从“monies”开始node one，7所以左上角的元素设置为零。上表中的空格对应infinity于数组中设置的值。

第2步

接下来，我们找到数组的最小值，这是 position 处的零(remaining money, node) = (7,1)。该元素设置为（使用与 相同大小visited的矩阵跟踪元素的状态），这意味着我们选择了。现在，所有连接到的节点都通过遍历相应的边来更新值。visitedArrayminArraynode onenode one

阵列一。

这minArray(6,3) = 191意味着我们已经走了一段距离191才能到达，node three而我们剩下的钱是6因为我们已经支付了1到达那里的费用。以同样的方式minArray(3,2)设置为190。红色方块标记该元素(7,1)已被访问。

第 3 步

现在我们再次找到最低的未访问元素（即minArray(3,2) = 190），将其设置为visited并更新所有连接到它的元素。这意味着距离累加，剩余的钱是通过从当前值中减去成本来计算的。

数组二。

请注意，返回node onefrom太昂贵了node two。

第4步

下一步，选择minArray(6,3) = 191看起来像这样。

阵列三。

第 5 步

三步后，数组看起来像这样。这里选择了两个相等的元素382和一个相等的元素383。请注意，元素的值仅在改进（即低于）当前值时才更新。

阵列四。

第 6 步

数组继续填充，直到所有元素都被访问或仍然具有无限值。

阵列 5。

最后一步

最后一步是通过找到第四列的最小值来找到总距离。我们可以看到，最小值minArray(0,4) = 385对应于正确的解决方案。

注意：如果第四列的所有值都是无限的，则意味着没有有效的解决方案。该算法还指定如果在第四列中有多个相等且最小距离的值，则选择最便宜的一个。

于 2013-01-14T13:30:27.167 回答
1

您可以制作节点之间的成本为 0 的副本，以添加第二条可能的路径。

像这样（伪代码）

Node 1____
|         |
|path1    |
|cost=3   |path2 cost=5
|         |
Node 2____/

变成这样：

Node 1____cost=0____Node 1a
|         path 1a     |
|path1                |path2
|cost=3               |cost=5
|                     |
Node 2________________/

不确定这是否可行，但这是一个想法。

于 2013-01-11T23:45:58.497 回答
1

我不认为 Dijkstra 的算法是解决这个问题的好方法，因为所需的距离不仅是源节点和目的地。这是一个基于 A* 搜索算法的解决方案。\

首先，执行基于weight然后基于的FolydWarshalladditional_data以获得图中每个节点对的最小值和最小值。weightadditional_data

  FloydWarshall(Weights);
  FloydWarshall(Additional_datas);

其次，我们基于优先级队列执行 A* 搜索，其元素如下结构（以 c 代码为例。）优先级队列将自动获取所有候选中的 weights_sum 最少。weights_expected 是通过当前节点到目标节点的路径的最佳猜测，而 weights_now 是当前权重

  struct NODE
    {
        int node;
        int weights_expected;
            int weights_now;
        int additional_datas_now;
            bool visited;
    };
    bool operator < (const NODE &A,const NODE &B)
    {
        return A.weights_expected>B.weights_expected || (A.weights_expected==B.weights_expected && 
   A.additional_datas_now>B.additional_datas_now);
    }

在 A* 搜索算法中，

1) we first put the source node into priority queue. 
  2) while Priority Queue is not empty:
        Set **A** equal to the head of priority queue and pop out the head of priority queue. 
        A.visited=True;
        if A is the destination node **Dest**, **return** A.weights_expected. 
        For each neighbors **B** of node **A**, 
          if A.visited==False **and** A.additional_datas_sum+|AB|.additional_data+Additional_datas[B][Dest]<=x, 
               1) B.additional_datas_now=A.additional_datas_now+|AB|.additional_data;    
               2) B.weights_now=A.weights_now+|AB|.weight;
               3) B.weights_expected=B.weights_now+Weights[B][Dest];
               3) push node B into priority Queue. 
   3) Print "Do not find a proper path" //if code came to here, that means the if in 2) do not return a value.

A* 搜索仍然是 NP 难的，因为在最坏的情况下它必须搜索每条可能的路径。然而，它比简单的 DFS 搜索要快得多，并执行大量搜索路径切割。

于 2013-01-07T21:30:14.600 回答
1

这个问题是NP完全的。没有一种算法比多人解释的算法更有效（Tom Anderson，user1884905）。

证明：通过减少非负数的子集和。

以子集和（N 个数字）的实例 A 为例。构建一个图，其中有 N+1 个节点。对于节点 i 和 i+1 ，制作 2 条路径，一条权重=0，additional_data=A[i]，另一条权重=A[i]，additional_data=0。选择 x（additional_data 总和的限制）。

观察到算法必须最小化权重之和，因此它也会最大化附加数据之和。因此，选择的第一类路径将是与子集和问题结果中的数字相关联的路径。

于 2013-01-17T16:36:22.737 回答
1

附加条件将破坏 Dijkstra。可以这样想：如果你在图中有一条路径 A->B 和一条边 B->C 在图中，那么涉及 B 的最短路径 A->C 肯定是 A->B 的最小路径->C。在您的情况下，此条件不成立，因为虽然 A->B 和 B->C 可能有效，但 A->B->C 可能无效。

好的，这就是你抓起一张纸试试这个的地方。

如果您查看您的图表，并假设您想要从 (1) 到 (4)，请注意如何通过引入以下边来消除 (3)：

  • (1)->(4), [390, 2]
  • (1)->(2), [383, 3]
  • (2)->(4), [391, 3]

一旦你消除了除直线之外的所有边，问题就变得更容易了：对于每个节点，你可以跟踪达到目标需要多少[距离，额外]。您不必存储额外的 > max 或 'remaining additional' < 0，因为这不是一个可行的解决方案。此外，如果您有多个相等的附加距离，则应仅保留最小距离。

现在最好的解决方案是在最后一个节点（或第一个，取决于您如何订购它）中距离最小的那个。如果在路上，你保留了你是如何到达那里的指针（例如，如果你更新矩阵中的值也存储使它改变的元素），你也可以回溯路径。

在这里您应该注意，当问题出现在您建议的矩阵的非消除形式时，您可以执行相同的操作：x 轴作为节点，y 轴作为“每个节点的列表”。

那应该这样做。

于 2013-01-16T08:53:42.540 回答
1

您的附加条件使问题变得更加困难。看着它，我认为你唯一能做的就是找出源和目标之间所有可能的路径，按总边权重对它们进行排序，然后一一检查你的附加条件是否成立。

然而，寻找两个顶点之间所有可能路径的问题是NP-Hard。稍加修改的 DFS 版本可能可以解决问题，但可能并非在所有情况下都如此。

于 2013-01-06T17:55:52.943 回答
1

您可以使用 bellman-ford 算法，假设您的附加数据是bellman-ford 算法中的边数参数。

于 2013-01-17T14:04:29.933 回答