时间戳

首页 > 解决方案 > SSSP 算法：最小距离但在一定数量的“跳”下

shortest-path - SSSP 算法：最小距离但在一定数量的“跳”下

问题描述

给定一个有向加权图（没有负边），从一个节点到另一个节点的最短距离是多少，它也满足从一个节点/顶点到另一个节点/顶点的“跳数”必须小于某个值 k 的条件. （其中 k 肯定小于节点数）。

一个“跳”被定义为从一个节点移动到另一个节点，并且“跳”值从源节点开始为 1。

问题并不像简单地运行 Dijkstra 算法那么简单，因为该算法只为您提供最短距离，而不考虑“跳数”。

考虑 1：从源到端节点的最短路径可能超过允许的最大“跳数”。

考虑 2：增强 Dijkstra 算法以最小化“跳数”的数量会给你一个可能的答案，但它可能不是最短的。

注意这里的优先级仍然是最小化最短距离，只是有一个“跳数”需要小于某个值的新条件。

标签： shortest-pathdijkstra

解决方案

有一种解决方案可以针对您的特定情况修改 Bellman-Ford 算法。在经典的 Bellman-Ford ( https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm ) 上，您应该进行 N 次迭代。

解决方案的思路如下，

为每个其他节点设置距离[root] = 0，距离 [x] = 无穷大。

现在，我们将遍历所有边并尝试改进我们的答案。

For Edge in Edges:
    distance[Edge.dest] = min( distance[Edge.dest], distance[Edge.src] + Edge.cost)

应用此步骤一次将为我们提供从原点到最多使用一条边的最短路径。现在的想法是准确地重复此步骤 K 次。这将为我们提供从原点到使用最多 K 条边的每个其他节点的最短路径。

复杂度： O( K * |edges| )

推荐阅读