Andrew Goldberg's Network Optimization Library

The software comes with no warranty, expressed of implied.

• CS2 contains an efficient implementation of a scaling push-relabel algorithm for the minimum-cost flow/transportation problems. For a detailed description and experimental data, see
  "An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm" by A. V. Goldberg, J. Algorithms 22 (1997), pages 1--29.
  Written in C.
  Available from IG Systems.
• paraF contains an implementation of an efficient parametric flow algorithm. For a detailed description and experimental data, see
  "Experimental Evaluation of a Parametric Flow Algorithm" by M. Babenko and A. V. Goldberg, Microsoft Research Technical Report MSR-TR-2006-77 2006.
  Written in C++.
  Available from Microsoft Research.
• HIPR is a new, more robust version of the hi-level variant of the PRF code h_prf (see below). In most cases, we recommend the new code over the old one.
  Written in C. The current version is 3.5.
  Copyright / HIPR (tar format).
• PRF contains an efficient implementations the push-relabel method for the maximum flow/minimum cut problems. For a detailed description and experimental data, see "On Implementing Push-Relabel Method for the Maximum Flow Problem," Algorithmica 19 (1997), 390 -- 410. In most cases, we recommend the new code, HI_PR, over the old one.
  Written in C. The current version is 1.8.
  Copyright / PRF (tar format).
• MLB contains efficient implementations of the multilevel bucket and smart queue algorithms for the single-source shortest path problem with nonnegative integral arc lengths. It also contains problem generators. For a detailed describtion and experimental data, see
  "Shortest Path Algorithms: Engineering Aspects" by A. V. Goldberg, proceedings of the International Symposium on Algorithms and Computation (ISAAC '01), Springer Lecture Notes in Computer Science (2001), and
  "A Simple Shortest Path Algorithm with Linear Average Time" by A. V. Goldberg, proceedings of the 9th European Symposium on Algorithms (ESA '01), Springer Lecture Notes in Computer Science LNCS 2161 (2001), pages 230--241.
  Written in C++. The current version is 2.1.
  Copyright / MLB (tar format).
• MINCUTLIB Contains codes and data sets for the minimum cut problem. For a detailed description and experimental data, see
  "Experimental Study of Minimum Cut Algorithms," C. S. Chekuri, A. V. Goldberg, D. R. Karger,M. S. Levine, and C. Stein, Technical Report 96-132, NEC Research Institute, Inc., 1996,
  Copyright / MINCUTLIB home page.
• BIM contains codes, generators, and generator inputs for bipartite matching and unit capacity flow algorithms. For a detailed description and experimental data, see our paper "Augment or Push? A computational study of Bipartite Matching and Unit Capacity Flow Algorithms," NEC Research Institute TR #98-036R , 1998.
  Copyright / BIM (compressed tar format).
• SPLIB contains codes, generators, and generator inputs for shortest path algorithms. For a detailed description and experimental data, see "Shortest Paths Algorithms: Theory and Experimental Evaluation," by B.V. Cherkassky, A.V. Goldberg, and T. Radzik, Math. Prog. 73 (1996), pages 129--174.
  Copyright / SPLIB (tar format).
• SPC contains codes, generators, and generator inputs for shortest path algorithms with negative cycle detection. For a detailed description and experimental data, see "Negative-Cycle Detection Algorithms," B. V. Cherkassky and A. V. Goldberg, Technical Report 96-029, NEC Research Institute, Inc., 1996.
  Copyright / SPC (tar format).
• CSA contains an efficient implementation of a scaling push-relabel algorithm for the assignment problem. For a detailed description and experimental data, see "An Efficient Cost Scaling Algorithm for the Assignment Problem," Math. Prog. 71 (1995), pages 153--178.
  Copyright / CSA (compressed tar).
• HQ contains implementations of Dijkstra's shortest path algorithm based on hot queue, multi-level buckets, and k-heap data structures, as well as problem generators. For a detailed description and experimental data, see
  "Buckets, Heaps, Lists, and Monotone Priority Queues," B.V. Cherkassky, A.V. Goldberg, and C. Silverstein, Technical Report 96-070, NEC Research Institute, Inc., 1996,
  "Implementations of Dijkstra's Algorithm Based on Multi-Level Buckets," A.V. Goldberg, and C. Silverstein, Technical Report 95-187, NEC Research Institute, Inc., 1995.
  Copyright / HQ (tar format).