对于网图来说, 最短路径, 是指两顶点之间经过的边上权值之和最少的路径, 并且我们称路径上的第一个顶点为源点, 最后一个顶点为终点最短路径的算法主要有迪杰斯特拉 (Dijkstra) 算法和弗洛伊德 (Floyd) 算法本文先来讲第一种, 从某个源点到其余各顶点的最短路径问题
这是一个按路径长度递增的次序产生最短路径的算法, 它的大致思路是这样的
比如说要求图 7-7-3 中顶点 v0 到 v1 的最短路径, 显然就是 1 由于顶点 v1 还与 v2,v3,v4 连线, 所以此时我们同时求得了 v0->v1->v2 = 1+3 = 4, v0->v1->v3 = 1 +7 = 8, v0->v1->v4 = 1+5 = 6
现在我们可以知道 v0 到 v2 的最短距离为 4 而不是 v0->v2 直接连线的 5, 如图 7-7-4 所示由于顶点 v2 还与 v4,v5 连线, 所以同时我们求得了 v0->v2->v4 其实就是 v0->v1->v2->v4 = 4+1=5,v0->v2->v5 = 4+7 = 11, 这里 v0->v2 我们用的是刚才计算出来的较小的 4 此时我们也发现 v0->v1->v2->v4 = 5 要比 v0->v1->v4 = 6 还要小, 所以 v0 到 v4 的最短距离目前是 5, 如图 7-7-5 所示
当我们要求 v0 到 v3 的最短路径时, 通向 v3 的三条边, 除了 v6 没有研究过外, v0->v1->v3 = 8, 而 v0->v4->v3 = 5 +2 = 7, 因此 v0 到 v3 的最短路径为 7, 如图 7-7-6 所示
如上所示, 这个算法并不是一下子就求出来 v0 到 v8 的最短路径, 而是一步步求出它们之间顶点的最短距离, 过程中都是基于已经求出的最短路径的基础上, 求得更远顶点的最短路径, 最终得到想要的结果
程序代码如下:(改编自大话数据结构)
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #include using namespace std; #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; } MGraph; typedef int PathArc[MAXVEX]; typedef int ShortPathTable[MAXVEX]; /* 构建图 & nbsp;*/ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges = 16; G->numVertexes = 9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 & nbsp;*/ { G->vexs[i] = i; } for (i = 0; i < G->numVertexes; i++)/* 初始化图 & nbsp;*/ { for ( j = 0; j < G->numVertexes; j++) { if (i == j) G->arc[i][j] = 0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } 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]; } } } /* Dijkstra 算法,求有向网 G 的 pos 顶点到其余顶点 v 的最短路径 P[v] 及带权长度 D[v] */ /* P[v] 的值为前驱顶点下标, D[v] 表示 pos 到 v 的最短路径长度和 & nbsp;*/ /* pos 取值 & nbsp;0~MG.numVertexs-1 */ void ShortestPath_Dijkstra(MGraph MG, int pos, PathArc P, ShortPathTable D) { int v, w, k, min; int final[MAXVEX];/* final[w]=1 表示求得顶点 pos 至 w 的最短路径 & nbsp;*/ for (v = 0; v < MG.numVertexes; v++) { final[v] = 0;/* 全部顶点初始化为未知最短路径状态 & nbsp;*/ D[v] = MG.arc[pos][v];/* 将与 pos 点有连线的顶点加上权值 & nbsp;*/ P[v] = 0;/* 初始化路径数组 P 为 0 */ } D[pos] = 0; /* 说明源点 pos 没有到自身的路径 & nbsp;*/ P[pos] = -1; /* -1 表示自身无前驱顶点 */ final[pos] = 1;/* pos 至 pos 不需要求路径 & nbsp;*/ /* 开始主循环,每次求得 pos 到某个 v 顶点的最短路径 & nbsp;*/ for (v = 1; v < MG.numVertexes; v++) { min = INFINITY;/* 当前所知离 pos 顶点的最近距离 & nbsp;*/ for (w = 0; w < MG.numVertexes; w++)/* 寻找离 pos 最近的顶点 & nbsp;*/ { if (!final[w] && D[w] < min) { k = w; min = D[w];/* w 顶点离 pos 顶点更近 & nbsp;*/ } } final[k] = 1;/* 将目前找到的最近的顶点置为 1 */ for (w = 0; w < MG.numVertexes; w++)/* 修正当前最短路径及距离 & nbsp;*/ { if (!final[w] && (min + MG.arc[k][w] < D[w])) { /* 说明找到了更短的路径,修改 D[w] 和 P[w] */ D[w] = min + MG.arc[k][w];/* 修改当前路径长度 & nbsp;*/ P[w] = k; } } } /* 结束循环,若 P[w] = 0; 说明顶点 w 的前驱为 pos */ } int main(void) { MGraph MG; PathArc P; ShortPathTable D; int i, j, pos = 2; CreateMGraph(&MG); ShortestPath_Dijkstra(MG, pos, P, D); cout << "逆序最短路径如下:" << endl; for (i = 8; i >= 0; i--) { j = i; while (P[j] != -1 && P[j] != 0) { cout << "v" << j << "<-" << "v" << P[j] << " "; j = P[j]; } cout << "v" << j << "<-" << "v" << pos << " "; cout << endl; } cout << endl; return 0; } |
输出为:
其中 CreateMGraph 函数创建出来的邻接矩阵如图 7-7-7 所示
相信经过上面的分析, 大家可以自己进行循环跑程序分析了, 循环结束后 final = { 1, 1, 1, 1, 1, 1, 1, 1, 1 }表示所有顶点均完成了最短路径的查找工作此时 D = { 4, 3, 0, 3, 1, 4, 6, 8, 12 }, 注意我们在前面说过 Dijkstra 算法可以求某个源点到其他顶点的最短路径, 现在我们上面程序中给出的 pos = 2, 即源点为 v2, 所以 D[2] = 0 表示没有到自身的路径 D 数组表示 v2 到各个顶点的最短路径长度, 比如 D[8] =1+2 + 3 + 2 + 4 = 12 此时 P = { 1, 0, -1, 4, 0, 4, 3, 6, 7 }, 可以这样来理解, P[2] = -1 表示 v2 没有前驱顶点, P[1] = P[4] = 0 表示 v1 和 v4 的前驱顶点为源点 v2 再比如 P[8] = 7, 表示 v8 的前驱是 v7; 再由 P[7] = 6, 表示 v7 的前驱是 v6; P[6] = 3 表示 v6 的前驱是 v3, 这样就可以得到 v2 到 v8 的最短路径为 v2->v4->v3->v6->v7->v8, 从上面的程序输出也可以验证我们的推测
其实最终返回的数组 D 和数组 P, 是可以得到 v2 到任意一个顶点的最短路径和路径长度的, 也就是说我们通过 Dijkstra 算法解决了从某个源点到其余各顶点的最短路径问题从循环嵌套可以得到此算法的时间复杂度为 O(n^2), 如果我们要得到任一顶点到其余顶点的最短路径呢? 最简单的办法就是对每个顶点都当作源点进行一次 Dijkstra 算法, 等于在原有算法的基础上, 再来一次循环, 此时整个算法的时间复杂度就为 O(n^3)
来源: http://www.bubuko.com/infodetail-2507269.html