各种应用通常要求图模型中的每条表与权重或者开销关联起来。在航空地图中，每一条边表示一条航线，这些边的权重表示距离或者费用。在这种情况下自然会出现求开销最小值的问题。我们可以将此类问题分成两类：查找最低开销途径将所有的点连接在一起和查找两个已知点之间的最小开销路径。我们可以用查找最小生成树来表示像第一类这样的无向图，这也是本文重点所要介绍的加权无向图以及最小生成树(MST)算法。