-1
$\begingroup$

I've been trying to solve the following problem:

Problem is the following: Given a graph and a pair of nodes $s$, $t$ you have to find the path from $s$ to $t$ which minimises the sum of its two largest edges.

Here's what i've come up with: I am executing the Prim algorithm with a slight modification. The cost of a node $u$ (i.e what's saved in the heap) is the following: Minimum sum of two largest edges that can lead from $s$ to $u$, where said edges are either on the tree constructed thus far (via Prim) or one of them can be an edge $e=(a,u)$ where $a$ is a node on the tree.

The reasoning of why this should work – I think – is similar to the Prim's algorithm proof. The problem reminds me of the Minimum Bottleneck Tree which can also be solved by MST.

However, the algorithm fails on three test cases. I've checked the source code for errors but I didn't find anything. This means that the error is likely in my algorithm. (Of course, I can post the code if needed.)

Can anyone either show a testcase where the algorithm fails or give a hint in the right direction?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I'm not quite sure what you're asking. You say you already have three test cases where the algorithm fails. Why do you want more? If you do post the algorithm, please use pseudocode, rather than just dumping the source. $\endgroup$
    – David Richerby
    Sep 13, 2014 at 9:42
  • $\begingroup$ i don't know the tests. Just the fact that my algorithm fails those. $\endgroup$
    – jjohn
    Sep 13, 2014 at 9:49

1 Answer 1

Reset to default
0
$\begingroup$

If my assumption on how you handle paths of length 1 is correct (the weight of the path is the weight of the single edge), your example should fail on the graph described by the following adjacency matrix:

$$\begin{matrix} &s&u&v&t\\ s&-&3&4&-\\ u&3&-&3&-\\ v&4&3&-&3\\ t&-&-&3&- \end{matrix}$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ You're right. I get 7 instead of 6. Thank you! $\endgroup$
    – jjohn
    Sep 15, 2014 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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