求解运输问题的一种新算法

摘要

本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijkstra算法扩展到可能出现负边权的运输问题.与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时).