49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
50 /// \cite amo93networkflows, \cite klein67primal, |
50 /// \cite amo93networkflows, \cite klein67primal, |
51 /// \cite goldberg89cyclecanceling. |
51 /// \cite goldberg89cyclecanceling. |
52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
54 /// It runs in strongly polynomial time O(n<sup>2</sup>m<sup>2</sup>log(n)), |
54 /// It runs in strongly polynomial time \f$O(n^2 m^2 \log n)\f$, |
55 /// but in practice, it is typically orders of magnitude slower than |
55 /// but in practice, it is typically orders of magnitude slower than |
56 /// the scaling algorithms and \ref NetworkSimplex. |
56 /// the scaling algorithms and \ref NetworkSimplex. |
57 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
57 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
58 /// |
58 /// |
59 /// Most of the parameters of the problem (except for the digraph) |
59 /// Most of the parameters of the problem (except for the digraph) |
131 SIMPLE_CYCLE_CANCELING, |
131 SIMPLE_CYCLE_CANCELING, |
132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
133 /// well-known strongly polynomial method |
133 /// well-known strongly polynomial method |
134 /// \cite goldberg89cyclecanceling. It improves along a |
134 /// \cite goldberg89cyclecanceling. It improves along a |
135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
136 /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)). |
136 /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$. |
137 MINIMUM_MEAN_CYCLE_CANCELING, |
137 MINIMUM_MEAN_CYCLE_CANCELING, |
138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
139 /// improved version of the previous method |
139 /// improved version of the previous method |
140 /// \cite goldberg89cyclecanceling. |
140 /// \cite goldberg89cyclecanceling. |
141 /// It is faster both in theory and in practice, its running time |
141 /// It is faster both in theory and in practice, its running time |
142 /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)). |
142 /// complexity is \f$O(n^2 m^2 \log n)\f$. |
143 CANCEL_AND_TIGHTEN |
143 CANCEL_AND_TIGHTEN |
144 }; |
144 }; |
145 |
145 |
146 private: |
146 private: |
147 |
147 |