最短路径问题求解

1、最短路径问题求解实验报告学院：计算机科学与技术学院班级:*学号：*姓名：*、实验目的1）以最短路径问题为例，掌握动态规划的基本设计策略；2）掌握dijkstra贪心法求解最短路径问题并实现；3）掌握动态规划方法Floyd算法求解最短路径问题并实现;4）分析实验结果。二、问题基本思想描述1、实验描述及目标（1）以下图作为输入，利用dijkstra贪心法获取由结点1到其余结点最短路 径长度，输出保存到外部文件dijkstra output1.txt（2） 然后改写你的程序，求得所有各点之间的最短距离；输出保存到文件 dijkstra output2.txt.（3）以上图作为输入，利用Floyd算法

2、求得所有各点直接的最短距离；输出保 存到文件 floyd output1.txt.2、Dijkstra算法（单源最短路径）Dijkstra算法主要解决单源最短路径问题，即在图中求出给定顶点到其它任 一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短 路径的最优子结构性质。（1）最短路径的最优子结构性质该性质描述为：如果P（i,j）=Vi.Vk.Vs.Vj是从顶点i到j的最短路 径，k和s是这条路径上的一个中间顶点，那么P（k,s）必定是从k到s的最短路 径。下面证明该性质的正确性。假设P(i,j) = Vi.Vk.Vs.Vj是从顶点i到j的最短路径，则有 P(i,j)=P(

3、i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定 存在另一条从 k 到s的最短路径P(k,s)，那么 P(i,j)=P(i,k)+P(k,s)+P(s,j)P(i,j)。则与 P(i,j)是从 i 到 j 的最短路径 相矛盾。因此该性质得证。(2)Dijkstra 算法由上述性质可知，如果存在一条从i到j的最短路径(Vi. Vk,Vj)，Vk是 Vj前面的一顶点。那么(Vi.Vk)也必定是从i到k的最短路径。为了求出最短 路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬 如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点V

4、i，那么当前 已知可得从 V0 到达 Vj 顶点的最短距离 distj=min(distj,disti+matrixij。根据这种思路，假设存在G=，源顶点为V0，U=V0,disti记录V0到i的最短距离，pathi 记录从V0到i路径上的i前面的一个顶点。从V-U中选择使disti值最小的顶点i，将i加入到U中；更新与 i 直接相邻顶点的 dist 值。 (distj=min(distj,disti+matrixij)知道U=V，停止。3、Floyd 算法(1)动态规划解析动态规划的最优化原理。作为整个过程的最优策略具有如下性质：无论 过去的状态和决策如何，对前面的决策所形成的当前状态而言

5、，余下的诸决策必 须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具 有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解， 非最优解对问题的求解没有影响。动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也 就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的 历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划 分各个阶段之后，阶段I中的状态只能由阶段I+1中的状态通过状态转移方程 得来，与其他状态没有关系，特别是与未发生的状态

6、没有关系，这就是无后效性。 从图论的角度去考虑，如果把这个问题中的状态定义成图中的顶点，两个状态之 间的转移定义为边，转移过程中的权值增量定义为边的权值，则构成一个有向无 环加权图，因此，这个图可以进行“拓扑排序”，至少可以按他们拓扑排序的顺 序去划分阶段。(2)Floyd算法描述Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我 们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要 为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)， Floyd算法加入了这个概念Ak(i,j):表示从i到j中途不经过索引比k大的点的最短路径。这个限制的

7、重要之处在于，它将最短路径的概念做了限制，使得该限制有机 会满足迭代关系，这个迭代关系就在于研究：假设Ak(i,j)已知，是否可以借此 推导出 Ak-1(i,j)。假设我现在要得到Ak(i,j)，而此时Ak(i,j)已知，那么我可以分两种情况 来看待问题：Ak(i,j)沿途经过点k；Ak(i,j)不经过点k。如果经过点k，那么很显然，Ak(i,j) = Ak-1(i,k) + Ak-1(k,j)，为什么 是Ak-1呢？因为对(i,k)和(k,j)，由于k本身就是源点(或者说终点)，加上我 们求的是Ak(i,j)，所以满足不经过比k大的点的条件限制，且已经不会经过点 k，故得出了 Ak-1这个值

8、。那么遇到第二种情况，Ak(i,j)不经过点k时，由于 没有经过点k，所以根据概念，可以得出Ak(i,j)=Ak-1(i,j)。现在，我们确信 有且只有这两种情况-不是经过点k，就是不经过点k，没有第三种情况了，条 件很完整，那么是选择哪一个呢？很简单，求的是最短路径，当然是哪个最短，求取哪个，故得出式子:Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j)现在已经得出了 Ak(i,j) = Ak-1(i,k) + Ak-1(k,j)这个递归式，但显然 该递归还没有一个出口，也就是说，必须定义一个初始状态，事实上，这个初始 状态取决于索引k是从0开始还

9、是从1开始，一般描述算法习惯用1做开始索引， 如果是以1为开始索引，那么初始状态值应设置为A0，A0(i,j)的含义即从i到 j的边的距离。也就是说，A0(i,j) = cost(i,j)。由于存在i到j不存在边的 情况，也就是说，在这种情况下，cost(i,j)无限大，故A0(i,j) = oo(当i到 j无边时)我们最终的目标是求dist(i,j)，即i到j的最短路径，如何把Ak(i,j) 转换为dist(i,j) ？这个其实很简单，当k=n(n表示索引的个数)的时候，即 是说，An(i,j)=dist(i,j)。那是因为当k已经最大时，已经不存在索引比k大 的点了，那这时候的An(i,j

10、)其实就已经是i到j的最短路径了。三、程序清单#include#include#define INFINITY 99#define N 6迪杰斯特拉算法和佛罗伊德算法typedef struct(int vexsN;/顶点向量int vexnum,acrnum;/图的定点数和弧数int adjNN;邻接矩阵graph;void shortest_dij(graph g,int v0);void shortest_floyd(graph g);void initGraph(graph *g)FILE *fp;/初始化定点数g-vexnum = N;邻接矩阵初始化，从文件读入矩阵if(fp = f

11、open(adj.txt,r)= NULL)(printf(can not open the filen);return;for (int i = 0; i N; i+)(for (int j = 0; j adjij);fscanf(fp,n)；fclose(fp);初始化的邻接矩阵for (i = 0; i N; i+)(for (int j = 0; j adjij);printf(n)；shortest_dij(*g,0);shortest_floyd(*g);void shortest_dij(graph g,int v0)(/pathv代表从v0到其余顶点v的最短路径，distv代

12、表其带权长度若pvw为true,则w是从v0到v当前求得最短路径上的顶点/finav为true当且仅当v属于s，即已经求得从v0到v的最短路径 FILE *fp;int pNN;int pathN;int distN;int finaN;int min,v;printf(请输入源节点n);scanf(%d,&v0);for(v = 0;v g.vexnum;v+)(finav = false;distv = g.adjv0v;for (int w = 0; w g.vexnum; w+)(pvw = false;设空路径if(distv INFINITY)(pvv0 = true;pvv =

13、true;distv0 = 0;finav0 = true;初始化，v0属于s集合开始主循环，每次求得v0到某个顶点v的最短路径，并将v加到s集合 for (int i = 1; i g.vexnum; i+)/其余 g.vexnum-1 个顶点(min = INFINITY;当前所知距v0顶点最近的距离for (int w = 0; w g.vexnum; w+)(if(!finaw)/w 在 V-S 中if(distw min) (v = w;min = distw;finav = true;离v0顶点最近的v加入s集合for (w = 0; w g.vexnum; w+) /更新当前最短

14、路径及距离(if(!finaw & (min+g.adjvw distw)(修改 distw和 Pw,w 属于 v-sdistw = min + g.adjvw;pathw = pathv;pww = true;if(fp = fopen(dij_output1.txt，w)= NULL)(printf(can not open the filen); return;printf (-从v0到所有顶点的最短路径为n);for (i = 0; i g.vexnum; i+)(fprintf(fp,v0 到顶点%5d 的距离为5dn，i,disti);printf(10dn,disti);fclo

15、se(fp); void shortest_floyd(graph g)(求有向网g中各对顶点v和w之间的最短路径pvw及其带权长度 dvw若pvwu为true，则u是从v到w当前求得最短路径上的顶点FILE *fp;int dNN;int pNNN;int pathNN;for (int v = 0; v g.vexnum; v+)/各对顶点之间初始已知路径及距离(for (int w = 0; w g.vexnum; w+)(dvw = g.adjvw;for (int u = 0; u g.vexnum; u+)(pvwu = false;if(dvw INFINITY)从 v 到 w

16、有直接路径(pvwv = true;pvww = true;for (int u = 0; u g.vexnum; u+)(for (int v = 0; v g.vexnum; v+)(for (int w = 0; w g.vexnum; w+)(if(dvu + duw dvw)从 v 经 u 到 w 的一条路径更短(dvw = dvu + duw;for (int i = 0; i g.vexnum; i+)(pvwi = pvui | puwi;if(fp = fopen(floyd_output.txt，w)= NULL)(printf(can not open the filen

17、);return;fprintf(fp,各对顶点的最短距离如下表，其中99代表两个顶点之间走不 通n);for (int i = 0; i N; i+)(for (int j = 0; j N; j+)(fprintf(fp,%10d,dij);fprintf(fp,n)；fclose(fp);void main()(/shortest_dij();graph g;initGraph(&g);printf(hello worldn);四、运行结果以上图为例，可得如下结果:1、邻接矩阵adj.txt - 本文件旧格式口萱看CV) 帮目面9 9 99 0 0 9 9 93 1 99 9 99 0 9 9 9 0 一I 9 1 9 9 59 9 9 9 149 95 9 9 91 _y _y _y 9 -y9 99 9 9 99 9 4-99999 9 9 9 99 2 9 9 9 92、Dijkstra算法结果dij_outpLitl.-txt -记事本=一(E)0 9 5 9 9 5112 2 2I蜀蜀蜀蜀&罔 -n = n 一一 n = n 一nf hth nf nf nf JJ- LnJ LnJ LnJ0 12 3 4 5占苫苫笆笆罟小顶顶顶顶顶顶ooooooV V V V V V3、Floyd算法结果floyd_outpuittxt -记事本立件日牖钝曰宿式登