求网络中任意两点最短路径 2

《求网络中任意两点最短路径 2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、“求网络中任意两点最短路径”问题解决思路文澜学院成思洁1204070159（一）问题研究价值及分类最短路径问题旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。在日常生活中，如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，哪一条路径的路途最短。最短路径问题也是地理信息系统网络分析中的最基本最关键的问题，在交通网络结构的分析，交通运输线路的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。算法具体的形式包括：（１）确定起点的最短路径问题：即已知起始结点，求最

2、短路径的问题。（２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。（３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。（４）全局最短路径问题：求图中所有的最短路径。（二）解决思路：Dijkstra算法算法简介：以起始点为中心向外层层扩展，直到扩展到终点为止。算法功能：在程序中设置一个二维数组来存储任意两个顶点之间的边的权值，用户可以将任意一个图的信息通过键盘输入，然后再输入要查找的两个顶点

3、，程序可以自动求出这两个顶点之间的最短路径。原理：输入一个带权有向图G=（Vi，E）,i={0,1,2…n}，Vi表示节点，E表示边。W是一个二维数组，用来存储约束条件，W[i,j]即是边(i,j)的权值。当(i,j)∈E时，W[i,j]为一个非负权值，表示从节点i到j有路径相连；否则表示没有路径相连，此时W[i,j]为无穷大。D[i]表示从指定节点到节点Vi的最短路径长度。设置一个顶点的集合S，开始时S中仅有指定节点，即源点，然后不断运用贪心的策略，调整非S集合中点的最短路径长度，找到当前的最短路径节点，将其加入到集合S中，当S集合包含了所有可到达

4、的节点，D[i]中的值即为指定节点到各Vi点的最短距离。每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。核心思想：首先，把所有节点分为两组。第一组包含已确定最短路径的节点；第二组包含尚未确定最短路径的节点。然后，按最短路径长度递增的顺序把第二组的节点转移到第一组中去，直到第一组中包含所有可

5、到达的结点为止。此时，第二组中的节点为不可到达节点。在这个过程中，总保持从指定节点到第一组各节点的最短路径长度都不大于从指定节点到第二组中任何节点的路径长度。实现流程图：（三）以算法形式（1）为例，演示详细步骤ABDEF632534235C如上图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图中，相邻顶点间的距离与图中的目视长度不能一一对等）步骤S集合中U集合中1进入A，此时S=此时最短路径A→A=0以A为中间点，从A开始找U=A→B=6A→C=3A→其他U

6、中的顶点=∞发现A→C=3的权值为最短2进入C，此时S=此时最短路径A→A=0，A→C=3以C为中间点，从A→C=3这条最短路径开始找U=A→C→B=5＜A→B=6此时到B权值为A→C→B=5A→C→D=6A→C→E=7A→C→其他U中的顶点=∞发现A→C→B=5的权值为最短3进入B，此时S=此时最短路径A→A=0，A→C=3,A→C→B=5以B为中间点，从A→C→B这条最短路径开始找U=A→C→B→D=10＞A→C→D=6A→C→B→其他U中的顶点=∞发现A→C→D=6的权值为最短4进入D，此

7、时S=此时最短路径A→A=0，A→C=3,A→C→B=5,A→C→D=6以D为中间点，从A→C→D这条最短路径开始找U=A→C→D→E=8﹥A→C→E=7A→C→D→F=9发现A→C→E=7的权值为最短5进入E，此时S=此时最短路径A→A=0，A→C=3,A→C→B=5,A→C→D=6,A→C→E=7以E为中间点，从A→C→E这条最短路径开始找U=A→C→E→F=12＞A→C→D→F=9此时到F权值更改为A→C→D→F=9发现A→C→D→F=9权值为最短6进入F，此时S=

8、>此时最短路径A→A=0，A→C=3,A→C→B=5,A→C→D=6,A→C→E=7,A→C→D→F=9U集