Problem Statement
In a previous post I presented an approach to solve the shortest path problem using different implementations of algorithms. The shortest path problem is a classic and important combinatorial optimisation problem. It often appears as a subproblem when solving difficult combinatorial problems like the multicommodity network flow (MCNF) problems.
The problem is to route a set of demands (commodities) through a network1 with limited arc capacities. The inherent assumption with the following implementation is that the commodities can be shipped in fractions, hence are divisible. Read the rest of this entry »
