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.