差集理论及组合数学中的理论方法文献综述

一 提法与背景：

最短路径问题。即寻找图中某两个特定节点间最短的路径长度。所谓图上的路径即从图中一个起始点到一个终止结点的所有结点序列，路径上的长度即所经过的边权和。最短路径问题在实际中的应用也非常广泛，例如一位旅客要从A城到B城，两城之间有许多路线，他希望选择一条途中中转次数最少的路线。假设图中每一站都要都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。类似于求迷宫的最短路径，只须从顶点A出发对图作广度优先搜索即可。但这是一类简单的最短路径问题。对于么某些休闲旅游的旅客来说，可能更关心的是如何花钱最少，对司机来说里程和速度则是他们感兴趣的信息。于是抽象出单源最短路径的问题的背景，从某个城市出发，能否到达其它各城市？走哪条路花钱最少？习惯上称给定的出发点即路径上的第一个顶点为源点，其它各点即路径上最后一个顶点为终点，则单源最短路径的一般提法为：从有向网中源点到其余各终点有否路径？其最短路径是什么？

二 应用与意义：管道铺设，线路安排，厂区布局，设备更新等。能大幅节省财力，资源。

三 解决方法：

（）对此问题计算机科学家Dijkstra提出最短路径长度递增的次序求从源点到个终点最短路径的算法。 那么该如何确定某个特定结点到其它所有结点的最短距离？我们不妨设有结点1到N,我们将要求从结点1出发到其它所有结点的最短路径长度。初始时，设结点1到其它所有结点的最短路径长度均为无穷大，我们立即确定由结点1到结点1的最短路径长度为0。设已经确定最短路径长度的结点的集合为K，于是将结点1加入该集合。现将问题一般化，假设集合K中已经保存了最短路径长度最短的前m个结点，他们是p1,p2,.pm,并已经得出他们的最短路径长度。那么第m 1近的结点与结点1的最短路径上的中间结点一定全部属于集合K，这是因为若最短路径上中间有一个不属于集合K的结点，则它的最短路径一定小于第m 1近的结点的最短路径长度，与距离小于第m 1近的结点的最短路径已经确定，这样的结点全部属于集合K矛盾。那么第m 1近结点的最短路径必是由以下两部分组成，从结点1出发由已经确定的最短路径到达集合K中某结点p2，再由p2经过一条边到达该结点。为此，我们遍历与集合K中结点直接相邻的边，设其为（U,V,C），其中U属于集合K,V不属于集合K，计算由结点1出发经过已经确定的最短路径到达结点U，再由结点U经过该边到达结点V的路径长度。该路径长度为已经确定的结点U的最短路径长度 C。所有与集合K直接相邻的非集合K结点中，该路径长度最短的那个结点即确定为第m 1近结点，并将改结点加入集合K。如此反复直到结点1到所有结点的最短路径全部确定。

综上可总结出算法

（1） 初始化，集合K中加入结点1，结点1到结点1的最短距离为0，到其他结点为无穷。

（2） 遍历与集合K中结点直接相邻的边（U,V,C）, 其中U属于集合K,V不属于集合K，计算由结点1出发经过已经确定的最短路径到达结点U，再由结点U经过该边到达结点V的路径长度。比较所有与集合K中结点直接相邻的非集合K结点该路径长度，其中路径长度最小的结点被确定为下一个最短路径确定的结点，其最短路径长度即为这个路径长度，最后将该集合并入集合K.

（3） 若集合K中已经包含了所有的点，算法结束，否则从复（2）。

（二） 另一种求相似问题的算法是Floyd算法，该方法是求图中任意一对顶点间的最短路径。核心思想是从图的带权邻接矩阵A=[a(i,j)] nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。