Skip to content

Network Flows Optimization - Shortest Path, Max Flow and Min Cost Flow Algorithms in Python

License

Notifications You must be signed in to change notification settings

infovillasimius/flows

Repository files navigation

flows

Python network flows optimization algorithms

Shortest Path

Label Setting Algorithms:

  1. Dynamic (for topologically ordered graphs)
  2. Dijkstra
  3. Dial - Dijkstra (with a circular queue)
  4. Radix Heap - Dijkstra (with a radix heap queue)

Label Correcting Algorithms:

  1. Generic Label correcting
  2. F.I.F.O. L.C.
  3. Deque L.C.
  4. Negative Cycle immune Label Correcting

Max Flow Algorithms:

  1. Ford Fulkerson - Labeling
  2. Pre flow - Push

Min Cost Flow Algorithms:

  1. Successive shortest path
  2. Cycle canceling

Others:

  1. Topological ordering
  2. Depth First Search
  3. Flow decomposition

Loading a graph: You need a text file with this structure:

  1. Adjacency matrix (node - node) dimension (ex. 5)
  2. Mass balance excess of nodes (ex. 25 0 0 0 -25)
  3. Adjacency Matrix (ex. 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 )
  4. Cost Matrix (ex. 0 7 6 0 0 0 0 6 4 0 0 0 0 2 2 0 0 0 0 1 0 0 0 0 0 )
  5. Capacity Matrix (ex. 0 30 20 0 0 0 0 25 10 0 0 0 0 20 25 0 0 0 0 20 0 0 0 0 0 )