指派问题与最短路径问题的相互关系

THE RELATIONS BETWEEN THE ASSIGNMENT PROBLEM AND SHORTEST PATH PROBLEM

尽管指派问题与最短路径问题是运筹学中的经典问题,也为大家所共知;但是,我们却很少知道这两个问题间的相互关系。本文揭示了两问题间的内在联系,进而使我们有可能利用指派问题的匈亚利法来解决最短路径问题。反之,亦可使用最短路径的解决问题方法来处理相应的指派问题。

Althrough we know well the assignment problem and the shortest path problem, we consider little the relations between them. In this paper we shall announce the relations and promulgate how to use the Hungarian method for the assignment problem to solve the shortest path problem. Conversely, it is similar.