这个算法叫什么？ (SSSP)

Question

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

伪代码：

给定源节点u和目标节点v
初始化整数 dp 数组，该数组存储相对于源节点到目标节点的最小距离。 dp[v]= 0，其他无限
初始化存储当前节点是否在我们正在考虑的路径上的布尔 onPath 数组。
初始化布尔访问数组，跟踪当前路径是否已完成（最初全部为 false）
初始化存储节点暂定值的int暂定数组。 (暂定[u] = 0)
return 函数(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];
}

我知道这个算法不会涵盖目的地是负循环的一部分的情况，但除此之外，算法有什么问题吗？如果不是，它叫什么？

Answer 1

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

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

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

y 的外邻居是 v，产生长度为 10 的 y->v 路径；和 x，但循环逻辑抑制了对这条弧的考虑，因此 y 被标记为已访问，距离为 10（不是 2）。结果我们错过了最短路径。

这个算法叫什么？ (SSSP)

What is this algorithm called? (SSSP)

algorithm

graph

graph-theory

shortest-path

cycle