Graph theory question, Java. Which algorithm to achieve the following

Question

I have a graph, with X nodes and Y edges. Weighted edges. The point is to start at one node, and stop at another. Now here comes the problem;

Visualize the problem. The edges are roads, and the edge weights are the max weight limits for vehicles driving on the roads. We would like to drive the biggest truck possible from A to B. So the maximum allowed weight for a truck taking a given path is the smallest weight of all of the edges in that path. I want the largest maximum allowed weight for all paths from A to B.

Can I use some sort of Dijkstra's algorithm for this problem? I'm not sure how to express this problem in the form of an algorithm that I can implement. Any help is much appreciated.

Update: I tested out somethings that didn't work for me. A node would have to have one max truck for every incoming edge.

Answer 1

Dijkstra's algorithm should work, but your "distance" in this case is a bit weird. Your "distance" is the maximum sized truck you can get to a node. Let's call that M[v] for a node v. You need to process nodes in order from largest M[v] to smallest M[v] (opposite of normal Dijkstra), and calculate for each edge e from v to w:

M[w] = max(M[w], min(e.weight, M[v]))

Answer 2

This sounds (almost) exactly like the maximum flow problem which can be solved efficiently using the Ford-Fulkerson algorithm.

As Keith has pointed out in a comment, maximum the algorithm has to be varied slightly to only find one path with maximized minimum path segment, since the truck can’t be split into multiple parts.

Answer 3

I think you're looking for this

Shortest path

edit: actually no you arent, and the maximum flow link is correct

Answer 4

So if I understand this correctly, you're asking "What is the biggest truck that can drive from A to B"

To apply Dijkstra's algorithm, you'll need a way to model "cost". If you want to use a standard implementation, you could assign the inverse of the weight to the cost. Thus, the highest cost edge is the one with the lowest maximum weight. Of course, since you're probably wanting to use nice integers, you can simply modify the comparisons instead of actually using the inverses.

Answer 5

You are looking to optimise a [http://en.wikipedia.org/wiki/Flow_network]. The capacity is the road's max weight limit; and the flow is the weight of the truck.

Answer 6

You could take a sort of minimum spanning tree approach. Connect nodes one edge at a time, highest-flow edges first, until A and B are connected. The last edge you added to the graph is the lowest-flow edge that you'll have to cross to get from A to B. Probably not the most efficient solution (O(N²) worst case), but at least it's straightforward.

Answer 7

This is neither shortest path problem, nor a max flow problem. There is actually no problem. He stated - want max weight for all paths A to B. So go generate all paths from A by BFS. For all paths ending at B get find min weight of path's edges.

Answer 8

Use Dijkstra's algorithm with the inverse of the maximum truck weight as edge cost, and the maximum of individual edge weights as total route cost.

i.e. edge_cost equals 1/(maximum truck weight allowed) the total_cost of a given route is the maximum of the individual edge_cost's of all the edges in the route.

Answer 9

Various answers above propose simply Dijkstra algorithm with a modified weight function. For example, w(e) = -c(e), or 'w(e) = 1/c(e)', where w(e) is the weight of an edge, used by the algorithm, and c(e) is the capacity of the edge in the original problem formulation.

These don't work.

One can easily create counter-examples that this would yield incorrect results. For example, consider the graph:

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

Assume the value of a ('distance of node a in the algorithm formulation) is zero. The two paths from a to d are equivalent in this problem. Yet, if we just negate the edge capacity, distance(d), using the long path, is (-3)+(-3)+(-3) = -9 while using the short path it would be -3. If we inverse the edge capacity, distance(d) using the long path would be (1/3)+(1/3)+(1/3)=1, while it would just be (1/3) using the short one.

What will work is modifying the relaxation step of the algorithm, i.e. instead of using the functions of addition (+) and less-than (<), using respectively functions min and greater-than (>), and use a max-heap instead of a min-heap. We could avoid the last two modifications if we negate the edge weights and use less-than, but no way we can avoid replacing +, since we need some operator @ where a @ a = a for all a values, whereas + only works for a=0.

So, the only correct answer I see is the very first one given, by Keith Randall.

A nice exercise would be to formally prove that the modified algorithm is correct. What needs to be proved is: - if u is the node with maximum value d(u) at any loop iteration, then no path involving unmarked nodes can create a path to u yield a distance larger than d(u).

Intuitively it is easy to see, since all other unmarked nodes have distance less than (or equal to) the distance of 'u' (because we choose u as the one with maximum distance), and the distance of the generated paths is produced by successive invocations of min, thus it can only grow smaller, not larger.