405 shortest path method \ref edmondskarp72theoretical. |
405 shortest path method \ref edmondskarp72theoretical. |
406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
408 |
408 |
409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient |
409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient |
410 implementations, but the other algorithms could be faster in special cases. |
410 implementations. |
|
411 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to |
|
412 several thousands of nodes) and on dense graphs, while \ref CostScaling is |
|
413 typically more efficient on large graphs (e.g. hundreds of thousands of |
|
414 nodes or above), especially if they are sparse. |
|
415 However, other algorithms could be faster in special cases. |
411 For example, if the total supply and/or capacities are rather small, |
416 For example, if the total supply and/or capacities are rather small, |
412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). |
417 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). |
413 |
418 |
414 These classes are intended to be used with integer-valued input data |
419 These classes are intended to be used with integer-valued input data |
415 (capacities, supply values, and costs), except for \ref CapacityScaling, |
420 (capacities, supply values, and costs), except for \ref CapacityScaling, |