6
$\begingroup$

I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge.

enter image description here

In the above graph, the easiest path from 1 to 2 is: 

1 > 3 > 4 > 2

Because the maximum edge weight is only 2. On the other hand, the shortest path 1 -> 2 has maximum weight 4.

So it's an MST problem. I am thinking I will use Kruskal's algorithm to build the tree, but I'm not sure how exactly. I will know the edges but how do I "reconstruct" the path? For example, given vertices 3 and 2, how do I know to go left (top) of right in the tree? Or do I try both ways?

| cite | improve this question | |
$\endgroup$
  • 4
    $\begingroup$ This problem is known as widest path (or bottleneck shortest path) problem (in its minimax flavor). Wikipedia has plenty of references to algorithms. $\endgroup$ – Raphael♦ Oct 8 '12 at 8:57
  • 1
    $\begingroup$ Oh, there was a duplicate. $\endgroup$ – Raphael♦ Oct 8 '12 at 20:19
  • $\begingroup$ Note that this can be done in linear time (faster than finding an MST). The basic idea is to binary search for the minimum K such that deleting edges of cost more than K leaves the graph connected. In addition, when you query a K and determine that it is big enough, you delete all edges of cost greater than K. When you query a K and determine it is too small, you contract all edges that have cost at most K. (You use median finding on the remaining edge costs to find the K to query.) $\endgroup$ – Neal Young Nov 21 '12 at 21:50
4
$\begingroup$

You're right; it's essentially a MST problem. First build the minimum spanning tree, then use breadth-first or depth-first search to find the unique path in the tree between the two vertices.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmm ... so I will have to BFS/DFS to from root to find the 1st node then BFS/DFS to find the 2nd node from the 1st? Is that efficient? I will be having a bunch of queries (pairs of nodes) to execute. Any optimization or ideas u can think of? $\endgroup$ – Jiew Meng Oct 8 '12 at 6:51
  • $\begingroup$ For a single pair of nodes, do a BFS from one node until you find the other to find the path between them. If you want all pairs, then you should do some preprocessing on the whole tree. If you number the nodes in the tree based on an in-order traversal, then you can navigate the tree like a binary search tree to find your way from one node to another. Although asymptotically, there's not much difference. BFS is linear time, which is the length of the path in the worst case. $\endgroup$ – Joe Oct 8 '12 at 7:09
  • $\begingroup$ Ok, its said that the possible source vertices is small (only 10 possible start vertices). So now what? Build a table of 10 x (total num of vertices) and populate them with the max weight to that vertex? by transversing the tree from each possible source vertex? $\endgroup$ – Jiew Meng Oct 8 '12 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.