Finding the path with the maximum minimum weight

Question

I am trying to develop an algorithm for finding a path in a directed graph. This is not an ordinary way, and I cannot find any links to anything similar to what has already been done.

I want to find the path with the maximum minimum weight.

those. 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 someone can develop a way to do this or just point me towards some kind of reference material, that would be incredibly useful :)

EDIT :: I seem to forget to mention that I'm trying to move from a specific vertex to another specific vertex. Here is a very important point: /

EDIT2 :: As indicated below, I must emphasize that the weights of the edges are not negative.

Answer 1

Use Prim or the Kruskal algorithm . Just change them so that they stop when they find out that the vertices associated with them are connected.

EDIT: you are asking for the maximum minimum, but your example looks as if you want the minimum maximum. In the case of a maximum minimum, the Kruskal algorithm will not work.

EDIT: the example is fine, my mistake. Then only the Prim algorithm will work.

Answer 2

I copy this answer and adding also the addition of my proof of the correctness of the algorithm:

I would use some Dijkstra's option. I took the pseudo code below directly from Wikipedia and only changed 5 little things:

• Renamed dist to width (from line 3)
• Initialize each width to -infinity (line 3)
• Initialize the width of the source to infinity (line 8)
• Set the termination criterion to -infinity (line 14)
• Updated update function and sign (line 20 + 21)

 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 width[v] := -infinity ; // Unknown width function from 4 // source to v 5 previous[v] := undefined ; // Previous node in optimal path 6 end for // from source 7 8 width[source] := infinity ; // Width from source to source 9 Q := the set of all nodes in Graph ; // All nodes in the graph are 10 // unoptimized – thus are in Q 11 while Q is not empty: // The main loop 12 u := vertex in Q with largest width in width[] ; // Source node in first case 13 remove u from Q ; 14 if width[u] = -infinity: 15 break ; // all remaining vertices are 16 end if // inaccessible from source 17 18 for each neighbor v of u: // where v has not yet been 19 // removed from Q. 20 alt := max(width[v], min(width[u], width_between(u, v))) ; 21 if alt > width[v]: // Relax (u,v,a) 22 width[v] := alt ; 23 previous[v] := u ; 24 decrease-key v in Q; // Reorder v in the Queue 25 end if 26 end for 27 end while 28 return width; 29 endfunction 

Some (manual) explanation of why this works: you start from the source. From there you have an infinite capacity for yourself. Now you check all source neighbors. Suppose the ribs do not have the same capacity (in your example, say (s, a) = 300 ). Then there is no better way to reach b , then through (s, b) , so that you know the maximum capacity of b . You continue to walk to the best neighbors of a known set of peaks until you reach all the peaks.

Proof of the correctness of the algorithm:

At any point in the algorithm there will be 2 sets of vertices A and B. The vertices in will be the vertices for which the correct path of maximum minimum capacity is found. And the set B has peaks for which we did not find the answer.

Inductive hypothesis . At each step, all the vertices in the set A have the correct path values ​​of the maximum minimum capacity for them. those. all previous iterations are correct.

The correctness of the base case : when the set A has only the vertex S. Then the value of S is equal to infinity, which is true.

In the current iteration, we set

val [W] = max (val [W], min (val [V], width_between (VW)))

Inductive step . Suppose that W is a vertex in the set B with the largest val [W]. And W was put out of the queue from the queue, and W the answer val [W] was set.

Now we need to show that every other SW path has a width of & lt; = val [W]. This will always be true, because all other ways to reach W will go through some other vertex (let's call it X) in B.

And for all other vertices X in the set B val [X] <= val [W]

Thus, any other path to W will be limited to val [X], which will never be more than val [W].

Thus, the current val [W] estimate is optimal and, therefore, the algorithm calculates the correct values ​​for all vertices.

Answer 3

You can also use the binary answer search paradigm. That is, do a binary search on the scales, checking for each weight w , whether you can find the path in the graph using only the edges of the weight greater than w .

The biggest w you can find (via binary search) gives an answer. Note that you only need to check if the path exists, so just search by width (first by depth) (O (| E |)), and not by the shortest path. Thus, this is O(|E|*log(max W)) in all, comparable with Dijkstra / Kruskal / Prim O(|E|log |V|) (and I cannot immediately see their proof).

Answer 4

This can be solved using the BFS style algorithm, however you need two options:

• Instead of marking each node as “visited,” you mark it with the least weight along the path you took to reach it.

For example, if I and J are neighbors, I have the value w1, and the weight of the edge between them is w2, then J = min (w1, w2).

• If you reach the marked node with the value w1, you may need to repeat it and process it if you assign a new value to w2 (and w2> w1). This is necessary to make sure that you get the maximum of all the lows.

For example, if I and J are neighbors, I have the value w1, J has the value w2, and the weight of the edge between them is w3, then if min (w2, w3)> w1, you should mark J and process all the neighbors again.

Answer 5

Well, answering my own question here, just to try and get a little feedback that I found in the preliminary solution that I developed before posting here:

Each node stores a "fragment of the path", this is the whole path to it so far.

0) set the current vertex to the initial vertex
1) Generate all path fragments from this vertex and add them to the priority queue
2) Remove the fragment from the top of the priority queue and set the current vertex to the final vertex of this path
3) If the current vertex is the destination vertex, return the path
4) goto 1

I’m not sure that this will find a better way, although I think the exit condition at the third step is a bit ambitious. However, I cannot think of a better exit condition, since this algorithm does not close the vertices (as many path fragments as possible can refer to the vertex), you cannot just wait until all the vertices are closed (for example, Dijkstra for example)

Answer 6

I'm not sure Prim will work here. Take this counterexample:

 V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 4), (4, 2)} weight function w: w((1,2)) = .1, w((2,3)) = .3 w((1,4)) = .2 w((4,2)) = .25 

If you use Prim to search for the path maxmin from 1 to 3, starting from 1, select the path 1 --> 2 --> 3 , and the maximum distance will reach the path that goes through 4.

Answer 7

You can still use Dijkstra!

Instead of using +, use the min () operator.
In addition, you will want to orient the heap / priority _queue so that the biggest things are on top.

Something like this should work: (maybe I missed some implementation details)

 let pq = priority queue of <node, minimum edge>, sorted by min. edge descending push (start, infinity) on queue mark start as visited while !queue.empty: current = pq.top() pq.pop() for all neighbors of current.node: if neighbor has not been visited pq.decrease_key(neighbor, min(current.weight, edge.weight)) 

It is guaranteed that whenever you get to node, you followed the optimal path (since you find all the possibilities in descending order and you can never improve your path by adding an edge)

The time frames are the same as Dijkstra - O (Vlog (E)).

EDIT: oh wait, this is basically what you posted. Lol