14*：图的应用(最短路径问题)：（迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法） |
您所在的位置：网站首页 › 求解v1到v8的最短路径是多少 › 14*：图的应用(最短路径问题)：（迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法） |
14*：图的应用(最短路径问题)：（迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法）
|
问题
迪杰斯特拉（Dijkstra）算法 /*用于存储最短路径下标的数组*/ typedef int Patharc[MAXVEX]; /*用于存储到各点最短路径权值的和*/ typedef int ShortPathTable[MAXVEX];弗洛伊德（Floyd）算法 //Patharc 父节点和 ShortPathTable 最短路径 都是二维数组; typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; 目录1：迪杰斯特拉（Dijkstra）算法 2：弗洛伊德（Floyd）算法 预备正文 最短路径 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径不用覆盖所有的点 1：迪杰斯特拉（Dijkstra）算法Dijkstra 的时间复杂度是 O(n^2) 1：算法特点:迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 2：算法的思路: 最短路径问题：给定一个带权有向图 D 与源点 v ，求从v 到 D 中其它顶点的最短路径。限定各边上的权值大于0。如何求得这些路径？迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点 v 到其它各顶点的最短路径全部求出为止。解决步骤描述： 设置辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点 v0到终点 vi的最短路径的长度； 初始状态：2.1. 若从源点 v0 到顶点 vi有边：dist[i]为该边上的权值；2.2. 若从源点 v0 到顶点 vi无边：dist[i]为∞。根据以上描述，可以得到如下描述的算法：假设用带权的邻接矩阵Edge[i][j]表示边(vi,vj)上的权值。若(vi,vj)不存在，则置Edge[i][j]为∞。S为已.找到从v出发的最短路径的终点的集合，它的初始状态为空集。1.初始化： S ← {v0 };dist[j] ← Edge[0][j], j = 1, 2, …, n-1;2.找出最短路径所对应的点 K：dist[k] == min { dist[i] }, i ∈ V- S ;S ← S U { k };3.对于每一个 i ∈ V- S 修改：dist[i] ← min{ dist[i],dist[k] + Edge[k][i] }；4.判断：若 S = V, 则算法结束，否则转2。 算法的精髓：S 集内的顶点是已经找到最短路径的顶点，V0 到 w 的最短路径只能通过 S 集内的顶点,迪杰斯特拉算法的时间复杂度为O(n*n)。3：执行步骤分析 把图用邻接矩阵存储起来 V0→V1→V2->V4->V3->V6->V7->V8
4：分步解释 1：从源点到其余各顶点的最短路径问题。
2：从V0开始找，找到V1，V0->V1 从V0开始向后依次(从未达到顶点中找,避免形成循环路径)找与V0连接的顶点：V1和V2，路径权重和如下： V0->V1：1 V0->V2：5 比较大小，取最短路径：V0->V1
3：从V1开始找到与V1向后连接的点，找到最短路径。V0→V1→V2 从V1开始向后依次(从未达到顶点中找,避免形成循环路径)找与V1连接的顶点：V2、V3、V4，路径权重和如下： V0→V1→V2=1+3=4， V0→V1→ V3=1+7=8， V0→V1→V4=1+5=6。 比较路径权重和的大小，取最短路径：V0→V1→V2 现在，我问v0到v2的最短距离，如果你不假思索地说是5，那就犯错了。因为边上都有权值，刚才已经有V0→V1→V2的结果是4，比5还要小1个单位，它才是最短距离，如下图所示。 
4：从V2开始找到与V2向后连接的点，找到最短路径。V0→V1→V2-V4
从V2开始向后依次(从未达到顶点中找,避免形成循环路径)找与V2连接的顶点：V4、V5，路径权重和如下： V0→V1→V2->V4=1+3+1=5， V0→V1→V2->V5=1+3+7=11， 比较路径权重和的大小，取最短路径：V0→V1→V2->V4
4：从V4开始找到与V4向后连接的点，找到最短路径。V0→V1→V2->V4->V3 从V4开始向后依次向后依次(从未达到顶点中找,避免形成循环路径)找与V4连接的顶点：V3、V6、V7、V5，路径权重和如下： V0→V1→V2->V4->V3=1+3+1+2=7， V0→V1→V2->V4->V6=1+3+1+6=11， V0→V1→V2->V4->V7=1+3+1+9=14， V0→V1→V2->V4->V5=1+3+1+3=8， 比较路径权重和的大小，取最短路径：V0→V1→V2->V4->V3
5：从V3开始找到与V3向后连接的点，找到最短路径。V0→V1→V2->V4->V3->V6 从V3开始向后依次向后依次(从未达到顶点中找,避免形成循环路径)找与V3连接的顶点：V6，路径权重和如下： V0→V1→V2->V4->V3->V6=1+3+1+2+3=10， 比较路径权重和的大小，取最短路径：V0→V1→V2->V4->V3->V6 6：从V6开始找到与V6向后连接的点，找到最短路径。V0→V1→V2->V4->V3->V6->V7 从V6开始向后依次向后依次(从未达到顶点中找，避免形成循环路径)找与V6连接的顶点：V7、V8，路径权重和如下： V0→V1→V2->V4->V3->V6->V7=1+3+1+2+3+2=12， V0→V1→V2->V4->V3->V6->V8=1+3+1+2+3+7=17， 比较路径权重和的大小，取最短路径：V0→V1→V2->V4->V3->V6->V7
7：从V7开始找到与V7向后连接的点，找到最短路径。V0→V1→V2->V4->V3->V6->V7->V8 从V6开始向后依次向后依次(从未达到顶点中找，避免形成循环路径)找与V6连接的顶点：V8，路径权重和如下： V0→V1→V2->V4->V3->V6->V7->V8=1+3+1+2+3+2+4=16， 比较路径权重和的大小，取最短路径：V0→V1→V2->V4->V3->V6->V7->V8
1：首先初始化三个数组
代码实现： #include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITYC 65535 typedef int Status; typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; /*用于存储最短路径下标的数组*/ typedef int Patharc[MAXVEX]; /*用于存储到各点最短路径权值的和*/ typedef int ShortPathTable[MAXVEX]; /*10.1 创建邻近矩阵*/ void CreateMGraph(MGraph *G) { int i, j; G->numEdges=16; G->numVertexes=9; for (i = 0; i < G->numVertexes; i++) { G->vexs[i]=i; } for (i = 0; i < G->numVertexes; i++) { for ( j = 0; j < G->numVertexes; j++) { if (i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITYC; } } G->arc[0][1]=1; G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3; G->arc[4][6]=6; G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7; G->arc[7][8]=4; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /*10.2 求得网图中2点间最短路径 Dijkstra 算法 G: 网图; v0: V0开始的顶点; p[v]: 前驱顶点下标; D[v]: 表示从V0到V的最短路径长度和; */ void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D) { int v,w,k,min; k = 0; /*final[w] = 1 表示求得顶点V0~Vw的最短路径*/ int final[MAXVEX]; /*1.初始化数据*/ for(v=0; v |
【本文地址】
今日新闻 |
推荐新闻 |