找到所有边缘的最小最高成本的算法是什么? [英] What is the algorithm that finds the minimal highest cost of all edges?

问题描述

我正在尝试解决一个问题，我需要找到从开始到到达目标节点的每步最低成本.我认为该算法存在，但找不到该算法的名称.在我正在处理的情况下，仅存在上升沿，并且可能存在周期. 这不是dijkstra的，因为我不是在寻找最低总成本，而是要找到代表所有步骤中最高成本的最低成本.

I'm trying to solve a problem where I need to find the minimal cost per step to get from a start to a goal node. I think this algorithm exists, but I can not find the name of this algorithm. In the case I am working on there are only positive edges and there could be cycles. It is not dijkstra's, because I am not looking for the total minimum cost, but for a cost that represents the minimal highest cost of all the steps.

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

In the following example this algorithm would thus output 3 as 3 is the highest minimal cost the algorithm can find a path for. And is thus not the minimal cost, as that would be 4.

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

*The start node is gray and the goal node is green.

我认为存在这样的算法，我曾尝试在Google上进行搜索，但到目前为止找不到该算法的名称.

I think such an algorithm exists, I have tried searching on google, but so far could not find the name of this algorithm.

推荐答案

可以通过对dijkstra进行简单的修改来解决.

This can be solved with a simple modification on dijkstra.

Dijkstra的工作方式始终是选择最低成本途径.我们知道，只要在图表中移动时路径成本永不减少(在您的情况下是这样)，我们就会始终按照从最低路径成本到最高路径成本的顺序进行迭代，从而找到最佳答案.我们只需要将cost函数修改为每个路径中的最大值，然后运行dijkstra.

Dijkstra works by always picking the minimum cost path. We know that as long as path costs never decrease as we move in the graph (this is true in your case), we'll always find the optimal answer by iterating in order from lowest to highest path cost. We just have to modify the cost function to be the maximum across each path and run dijkstra.

这是一个伪代码(基本上是python)实现:

Here's a pseudocode (basically python) implementation:

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

这篇关于找到所有边缘的最小最高成本的算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！