vlambda博客
学习文章列表

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

最小生成树问题与最短路径问题相似，但它的目标是将网络中所有的节点连接起来，从而使总的分支长度达到最短。

同样是求各边权值之和最小，最小生成树与最短路问题有什么区别呢？

1. 最小生成树能保证连通所有节点的路径之和最小，但不能保证任意两点之间是最短路径。

2. 一般而言，最小生成树针对无向图，最短路问题针对有向图。针对无向图的最短路问题很容易扩展到有向图上，但在有向图上求一个给定树根的最小生成树（有向树）比求无向图中的最小生成树复杂得多。

在物理网络设计方面，架设通往各个乡镇的通讯设施，且要求建设成本最小的问题，是最小生成树问题的一个典型应用。本文介绍如何用 MQ for Windows已有的模块求解此类问题。