I'd like to preface this that this question is similar, but my question doesn't involve randomness, just finicky determinism, so the answer of use a known seed doesn't really apply. Likewise, this question is similar, but again, I'm not expecting the algorithm to ever fail -- I just don't know which way it will be correct.This question came about while testing graph algorithms. but is by no means limited to them. Some algorithms such as A* can have multiple correct answers. Depending on your exact implementation you may get any one of several answers, each of which are equally correct. This can make them difficult to test, though, because you don't know which one it's going to spit out ahead of time, and it's very time consuming to compute the answers by hand.In my specific case, I got around it by modifying Floyd-Warshall to spit out every possible shortest path, and spent the time hand testing that. It had the benefit of being a good feature in its own right. Then I could test other functions in terms of the known correct paths from FW (if the returned path is any one of the paths returned by FW for that start/end pair, it's correct). Of course, this only works for dense graphs due to how FW works, but it's still nice.However, that may not always be viable for all algorithms with this characteristic. So far, the best answer I've come up with is to test for the characteristics of a correct answer, rather than the correct answer itself. To go back to shortest path algorithms, you can check the cost of the returned path against the known right cost and make sure the path is valid.This works, but it can run the risk of not verifying everything correctly the more criteria for correctness there are, especially if the verification is itself complex (e.g. while correct algorithms exist, verifying a minimum spanning tree is a known hard problem; probably harder than constructing the MST itself), in which case you now have to extensively test your testing code. Worse: presumably you have to construct an MST to test an MST verification algorithm so you now have a great scenario where your MST test relies on your MST verification algorithm working, and your MST verification algorithm test relies on your MST generation code working.Finally, there's the cheap way, which involves observing the output, verifying it by hand, then hard coding the test to test the output you just verified, but that's not a great idea since you may have to revise the test every time you change the implementation a little (which is what automated testing is supposed to avoid).Obviously the answer depends on the exact algorithm you're testing to a degree, but I was wondering if there were any best practices for verifying algorithms that have several definite, deterministic correct outputs, but those precise correct outputs are difficult to know ahead of time, and possibly hard to even verify after the fact.
Testing (deterministic) algorithms with multiple or difficult to prove correct right answers
unit testing
I'm not sure you are trying to test the correct property, and this causes your ambiguity.Graph algorithms do not aim at finding some shortest path (this is a side effect), but to minimize or maximize some cost function defined on the set of edges and vertices.Thus, you can check the correctness of a solution by testing for the final value of this functional and asserting that the first and last nodes are the ones actually required.If you can pre-compute the final cost function value for each possible path (usually unrealistic), then you just have to check that the cost of the solution provided by the implementation under test is equal to the minimum cost among this set (absolute comparison).If you just have a gold standard algorithm and/or implementation, then you should compare the cost of its output with the one of the algorithm under test (relative comparison)For example, a naive test setup would be:Compute all possible paths between Va and Vb in the test graph with a greedy algorithm.Compute the cost function (for example, the length if all your edge weights are equal to 1) for each of these paths and find the minimum value.Apply the algorithm under test.Make an assertion in your unit test that the tested algorithm cost value is equal to the minimum of the greedy solutions.If you want to know more about graph based optimization, you can have a look at Yuri Boykov's publications here, though in another context (Computer Vision problems).