Teste seu programa para vários exemplos, inclusive exemplos de grande porte, com pelo menos 1000 vértices e 100000 arcos. Compartilhe seus testes! Quando você tiver testes com respostas corretas, envie-me seus resultados: arquivo-teste, solução ótima, tempo de processamento (dizendo em que máquina). Manterei nesta página uma lista com os resultados que certamente facilitará os testes de todos.
Para verificar se sua resposta está correta você pode utilizar o programa CPLEX (ou soplex) que resolve problemas de programação linear. Para transformar o arquivo acima em um arquivo ".lp" (formato que o CPLEX e o soplex esperam), fiz um programa em C que pode ser visto no link abaixo: