vlambda博客
学习文章列表

网络流问题是一类特殊的线性规划问题，如前面提到过的运输问题，除了可以写成线性规划的形式，还能将该问题构建成网络的形式求解。今天介绍网络流基本问题之一的 最短路径问题 的QM for Windows求解方法。

最短路径问题是确定初始点与几个目标点之间的最短距离。在生产实践，运输管理中，诸如工艺路线安排，管道线网铺设、设备更新等问题都可建模为最短路问题。经典的求解算法有基于最优性原理的标号法的 算法。而本文主要介绍如何用MQ for Windows已有的模块求解此类问题。

例： 在1号小区有一个快递网点，快递小哥需要给位于8号小区的顾客派件，途中可能会经过若干个小区。为提高配送效率，快递小哥需要选择一条 最快的路径 到达8号小区。（我们将上述问题抽象成下图所示的网络图，弧上的权值表示小区间的距离，这种弧上有权值的图称为赋权图。该问题可以基于图论的方法在网络上求解）。