从一个源点出发，经过N条边的最短路径

Question

在我的经济学研究中，我目前正在处理一个特定的最短路径问题：

给定一个带权边的有向确定性动态图，我需要找到从源点S出发通过N条边的最短路径。该图可以有环，边权可以为负数，并且路径允许多次经过一个顶点或边。

是否有一种高效的算法解决这个问题？

- AlexC75

---

有目标节点吗？ - Onk_r

你能澄清一下“经过N条边”的意思吗？你是指恰好经过N条边吗？（还是至少N条边） - Hans Olsson

没有目标节点，路径的唯一约束是它们经过恰好N个边。 - AlexC75

为了说明这个想法：所有的顶点都是经济的“状态”。如果存在一种“决策”可以使经济在每个时间步骤中从一个状态跳转到另一个状态，则两个顶点之间将通过一条边相连。因此，您可以通过“什么也不做”的决策停留在同一个状态（同一个顶点）。每个决策都有一个随时间变化的“成本”，这由边上的动态权重进行建模。我正在寻找经济可以在N个决策（因此每个时间步骤有一个决策）和因此N个边后走过的路径。 - AlexC75

交叉发布：https://cs.stackexchange.com/q/93620/755，https://dev59.com/Fqzka4cB1Zd3GeqP94fi。请勿在多个网站上发布相同的问题。每个社区都应该有一个诚实的机会回答问题，而不浪费任何人的时间。 - D.W.

Answer 1

一种可能的方法是：

首先在图中找到最小的边权重。

然后建立一个优先队列，其中包括从起始边开始的所有路径（最初为空路径从起始点开始），其中所有尚未处理的边都被计算为具有最低权重。

主循环：

1. 从队列中删除具有最低权重的路径。 2. 如果路径具有 N 条边，则完成。 3. 否则，将该路径的所有可能的单边扩展添加到优先队列中。

然而，这个简单的算法存在一个缺陷 - 你可能会多次访问同一个顶点作为第 i 条边（作为第二条和第四条是可以的，但在两条不同的路径中作为第四条是有问题的），这是低效的。

该算法可以通过在上述第三步中跳过它们来改进，因为优先队列保证到达该顶点的第一部分路径具有到该顶点的最低权重总和，并且其余部分路径不依赖于到达该顶点的方式（因为边和顶点可以重复）。

- Hans Olsson

Answer 2

“恰好有N条边”的限制使得这个问题比没有该限制的问题容易得多。基本上，您可以解决N = 0（只是起始节点），然后使用它来解决N = 1（起始节点的所有邻居），然后是N = 2（解决N = 1的邻居，对于连接到多个节点的节点，采用最低成本路径），以此类推。

伪代码（使用{field: val}表示“具有名为field且值为val的字段的记录”）：

# returns a map from node to cost, where each key represents 
# a node reachable from start_node in exactly n steps, and the
# associated value is the total cost of the cheapest path to 
# that node
cheapest_path(n, start_node):
  i = 0
  horizon = new map()
  horizon[start_node] = {cost: 0, path: []}
  while i <= n:
    next_horizon = new map()
    for node, entry in key_value_pairs(horizon):
      for neighbor in neighbors(node):
        this_neighbor_cost = entry.cost + edge_weight(node, neighbor, i)
        this_neighbor_path = entry.path + [neighbor]
        if next_horizon[neighbor] does not exist or this_neighbor_cost < next_horizon[neighbor].cost:
          next_horizon[neighbor] = {cost: this_neighbor_cost, path: this_neighbor_path}
    i = i + 1
    horizon = next_horizon
  return horizon

我们使用edge_weight(node, neighbor, i)来考虑动态权重，意思是“在时间步骤i从node到neighbor的花费”。

这是单源最短路径算法（如Dijkstra算法）的退化版本，但它更简单，因为我们知道我们必须恰好走N步，所以我们不需要担心被困在负权重循环中，或者更便宜的路径等等。

- jacobm

---

我不确定这是否适合。权重有其自身的动态，这意味着在经过第一条边后，所有边上的权重都可能会变化。因此，我认为像这样对邻居进行连续分析是行不通的。 - AlexC75

在这种情况下，我不明白为什么按照给定的算法（假设edge_weight考虑了动态边缘成本，因此称其为edge_weight(node, neighbor, i)）不能工作。你看到了我没有看到的东西吗？ - jacobm

不，我的算法认为A的成本为0。我们在每一步中都保留并处理到达每个节点的成本，而不仅仅是最便宜的节点。因此，地平线0是{A:0}（只有起始点），地平线1是{A:2，B:1，C:4}（使用T1权重到达每个节点的最便宜成本，从地平线0开始），地平线2是{A:0，B:3，C:2}（使用地平线1开始的T2权重的最便宜扩展）。 - jacobm

这个方法能否提供最终路径而不仅仅是最终视野？非常感谢您的帮助！我不确定您如何考虑边缘的动态性？ - AlexC75

更新了我的答案，添加了路径并明确了动态边权重。 - jacobm