这个算法叫什么名字？（SSSP）

Question

这个算法叫什么名字？（SSSP）

algorithmgraphgraph-theoryshortest-pathcycle

3

观察：对于每个节点，我们可以重用它到目的地的最小路径，因此我们不必重新计算它(dp)。另外，当我们发现一个循环时，我们检查它是否为负。如果不是，它将不会影响我们的最终答案，并且我们可以说它与目的地没有连接（无论它是否连接）。

伪代码：

- 给定源节点u和目标节点v - 初始化整数dp数组，存储相对于源节点到目标节点的最小距离。dp[v] = 0，其他一切都是无限的。 - 初始化布尔型onPath数组，表示当前节点是否在我们考虑的路径上。 - 初始化布尔型visited数组，跟踪当前路径是否已经完成（最初全部为假）。 - 初始化int tentative数组，存储节点的试探值。 (tentative[u] = 0) - 返回function(u)。

int function(int node){

   onPath[node] = true;

   for each connection u of node{

      if(onPath[u]){ //we've found a cycle
         if(cost to u + tentative[node] > tentative[u]) //report negative cycle
         continue; //safely ignore
      }

      if(visited[u]){
         dp[node] = min(dp[node], dp[u]); //dp already calculated

      }else{
         tentative[u] = tentative[node] + cost to u
         dp[node] = min(function(u), dp[node])
      }

      visited[node] = true;
      onPath[node] = false;
      return dp[node];
}

我知道这个算法不能覆盖目的地是负环的情况，但除此之外，算法还有什么问题吗？如果没有问题，它叫什么名字？

- timg

不确定您的代码是否正确，但伪代码中的思想与Bellman-Ford算法非常相似。https://cp-algorithms.com/graph/bellman_ford.html - Photon

事实上，我在学习贝尔曼-福德算法时想到了这个算法。每次都需要考虑所有的边，这似乎有点低效。 - timg

Bellman-Ford算法有一种修改版，实际上速度更快（尽管最坏时间仍然相同）。详情请见：https://cp-algorithms.com/graph/bellman_ford.html#toc-tgt-8 - Photon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

你不能“安全忽略”一个正权和循环，因为它可能隐藏着一条更短的路径。例如，假设我们有一个带有弧 u->x (10), u->y (1), x->y (10), y->x (1), x->v (1), y->v (10) 的图。最短的 u-v 路径是长度为 3 的 u->y->x->v。

在一个糟糕的执行中，前三个调用看起来像这样：

function(u)
    function(x)
        function(y)

< p > y 的出边邻居是 v，形成长度为 10 的 y->v 路径；还有 x，但循环逻辑抑制了对该弧的考虑，因此将 y 标记为已访问，距离为 10（而不是 2）。结果我们错过了最短路径。