What is the algorithm that finds the minimal highest cost of all edges?

user_4884368 0
Viewed 215

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.

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. Example of algorithm that I am looking for

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

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

nodes path algorithm
2 Answers

This can be solved with a simple modification on 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.

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
user_81121380

Well I have only heard about such problem for un-directed graphs, for directed ones (like your example) I do not know how it's called, yet its not hard to think up some efficient way to solve it:

  1. We can just binary search for the answer, initial search space is [0, maxWeightInWholeGraph]

  2. During each iteration of binary search we pick some middle value m and we need to check if there exist a path from start node to goal node with edge weights <= m

  3. This can be done by simple BFS, only traversing allowed edges

  4. Now we divide our search space by half choosing left part if we found start-goal path and right part otherwise.

  5. continue the binary search till we converge to answer

Complexity of this approach: O( (|V| + |E|) * log2(maxWeightInWholeGraph) )

user_40591450
Related