Find path between two nodes in graph, according to

问题:

I have the following problem. I have cyclic, undirected, weighted graph G=(V,E). I need to find the simple path (without cycles) between two given nodes according to these rules:

1. Finding minimal weight value in edges set of each possible path
2. Select this path, which has maximal min value among selected minimal values from found paths

E.g we have graph presented below:

We can try to find simple path from node 1 to node 8. There are two possible pathes, listed below:

1. 1 -> 3 -> 5 -> 8, minimal edge weight on this path is 2
2. 1 -> 3 -> 5 -> 6 -> 7 -> 8, minimal edge weight on this path is 283

According to presented criteria, wanted path is path number 2, because it has greater minimal value, than path no 1.

One important assumption: the number of nodes in graph are very small: less than 15.

I thought about Dijkstra or Bellman-Ford algorithm modification, but the challenge is, that we don't have local criteria (the min distance) - we cannot find minimal weight of edge, until we don't obtain whole path...

My second think was to use modification of Nearest-Neighbor algorithm, but it's used for solving so called travelling salesman problem, which is a little different case comparing to mine.

My question is following. Is it better way to solve this problem, than use Depth-First Algorithm to obtain all direct acyclic simple paths between two given nodes and next select max value of min weight values of each found path?

In such case I'm a little worried about complexity of DFS algorithm, especially due to recursion and number of possible connections (edges) in graph.

Thank you for any ideas.

回答1:

Use binary search on the minimal edge weight:

Assume your search interval is [m, M]. For a set value L = (m + M) / 2, use BFS or DFS to find a path from source to destination such that all edges have weight >= L. If you can do this, set m = L + 1 and repeat the search. If you cannot do this, set M = L - 1 and repeat the search.

This will be O((edges + nodes) log maxEdgeWeight). Should be very fast for your small number of nodes.

Note that there is a way to do it without the log factor as well, by using the ideas of Dijkstra's algorithm and counting sort. But you definitely do not need this for so few nodes.

Update 1:

Here is how this would work on your example. First of all, your search interval will be [2, 9000], since these are your min and max edge weights, respectively.

L = (2 + 9000) / 2 = 4501
=> Find a path from 1 to 8 such that all of its edges have weight >= 4501.
   This is not possible, so reduce the search interval to [2, 4500].

L = (2 + 4501) / 2 = 2251
=> Find a path from 1 to 8 such that all of its edges have weight >= 2251.
   This is not possible, reduce the search interval to [2, 2250]

L = (2 + 2250) / 2 = 1126
=> Not possible to find a path, reduce to [2, 1125]

L = (2 + 1125) / 2 = 563
=> Not possible, reduce to [2, 562]

L = (2 + 562) / 2 = 282
=> Success! We can find 1 -> 3 -> 5 -> 6 -> 7 -> 8
Mark 282 as the current best answer, and keep searching in [283, 562].

Eventually, you will be left with 283 as the answer, which is what you want. Then just print any path with all edge weights >= 283 (only one in your case).

回答2:

Find a maximum spanning tree (via the usual algorithms with the priority queue/sort order reversed) and take the unique path in it. The min edge on this path never would have been added to the tree if there were a path between its endpoints consisting of greater edges, as there would be if there were a better overall path.