时间戳

首页 > 解决方案 > 找到所有边的最小最高成本的算法是什么？

algorithm - 找到所有边的最小最高成本的算法是什么？

问题描述

我正在尝试解决一个问题，我需要找到从开始到目标节点的每一步最小成本。我认为这个算法存在，但我找不到这个算法的名称。在我正在研究的情况下，只有积极的边缘，并且可能存在周期。这不是 dijkstra 的，因为我不是在寻找最低总成本，而是在寻找代表所有步骤中最低最高成本的成本。

在以下示例中，该算法将因此输出 3，因为 3 是该算法可以找到路径的最高最小成本。因此不是最低成本，因为那将是 4。 我正在寻找的算法示例

*起始节点为灰色，目标节点为绿色。

我认为存在这样的算法，我曾尝试在 google 上搜索，但目前找不到该算法的名称。

标签： algorithmpathnodes

解决方案

这可以通过对 dijkstra 的简单修改来解决。

Dijkstra 通过始终选择最低成本路径来工作。我们知道，只要我们在图中移动时路径成本永远不会减少（在您的情况下是这样），我们总是会通过从最低到最高路径成本的顺序迭代来找到最佳答案。我们只需要将成本函数修改为每条路径的最大值并运行 dijkstra。

这是一个伪代码（基本上是python）实现：

import priority_queue

def min_cost_path(start, end):
    min_heap = priority_queue([[0, start]]) # queue in form of (cost, node)
    visited = set()

    while min_heap:
        # get lowest weight path thus far
        # cost is the lowest cost possible to get to node
        cost, node = min_heap.pop()
        # optimal path to this node has already been found, ignore this
        if node in visited: continue
        if node == end: return cost
        # this node has been visited
        visited.add(node)
        # add candidate node-weights to the queue
        for weight, neighbor in neighbors(node):
            if neighbor not in visited:
                min_heap.push((max(weight, cost), neighbor))

    return -1 # not possible

推荐阅读