The minimum cost network flow problem, (MCNFP) constitutes a wide category of networkflow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) forthe MCNFP has been developed. This algorithm belongs to a special “exterior point simplextype” category. Similar to the classical dual network simplex algorithm (DNSA), thisalgorithm starts with a dual feasible tree-solution and after a number of iterations, itproduces a solution that is both primal and dual feasible, i.e. it isoptimal. However, contrary to the DNSA, the new algorithm does not always maintain a dualfeasible solution. Instead, it produces tree-solutions that can be infeasible for the dualproblem and at the same time infeasible for the primal problem. In this paper, we presentfor the first time, the mathematical proof of correctness of DNEPSA, a detailedcomparative computational study of DNEPSA and DNSA on sparse and dense random probleminstances, a statistical analysis of the experimental results, and finally some newresults on the empirical complexity of DNEPSA. The analysis proves the superiority ofDNEPSA compared to DNSA in terms of cpu time and iterations.