Search code examples
algorithmgraphgraph-theorypath-findingdirected-graph

Finding the path with the maximum minimal weight

I'm trying to work out an algorithm for finding a path across a directed graph. It's not a conventional path and I can't find any references to anything like this being done already.

I want to find the path which has the maximum minimum weight.

I.e. If there are two paths with weights 10->1->10 and 2->2->2 then the second path is considered better than the first because the minimum weight (2) is greater than the minimum weight of the first (1).

If anyone can work out a way to do this, or just point me in the direction of some reference material it would be incredibly useful :)

EDIT:: It seems I forgot to mention that I'm trying to get from a specific vertex to another specific vertex. Quite important point there :/

EDIT2:: As someone below pointed out, I should highlight that edge weights are non negative.

Solution

  • Use either Prim's or Kruskal's algorithm. Just modify them so they stop when they find out that the vertices you ask about are connected.

    EDIT: You ask for maximum minimum, but your example looks like you want minimum maximum. In case of maximum minimum Kruskal's algorithm won't work.

    EDIT: The example is okay, my mistake. Only Prim's algorithm will work then.