While doing the "Djikstra" problem in the qualification round of Google's Code Jam this year, I had the problem of trying to verify my program. The standard method I use to do this kind of task is to write TWO programs which do the same thing in completely different ways. You then run both on the input. If the output differs between the two programs, you know have a bug in one or both of the programs. The disadvantage of this method is that the programmer has to create two programs, effectively doubling the time spent.
Are there better/more efficient methods for verifying that a program is correct, compared to writing multiple versions of the program and running them against each other?
Note that you only have this problem when the correct output is unknown and you have no way of generating validating input-output sets. If you know a priori what the output should be for any given set of input, then it is easy to verify a program. So, the question only applies to situations where you do not know what the correct output should be, you only know the specification for the process which the program is supposed to do.
In the case of the Dijkstra problem, I could have written a "test data generator" which went backwards from output to generate a known input state. By doing this, I could have created test data sets by a writing a second program, but one that would have been much simpler than the solver, therefore much less work than writing two solvers, however, for the sake of argument, let's suppose this option wasn't available.
