c 语言网站建设,一个简单的html网页,seo网络推广方法,wordpress展示页面模板下载目录
一、最短路径
二、迪杰斯特拉算法
三、弗洛伊德算法 一、最短路径
假若要在计算机上建立一个交通咨询系统#xff0c;则可以采用图的结构来表示实际的交通网络。如下图所示#xff0c;图中顶点表示城市#xff0c;边表示城市间的交通联系。 这个咨询系统可以回答旅…目录
一、最短路径
二、迪杰斯特拉算法
三、弗洛伊德算法 一、最短路径
假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。如下图所示图中顶点表示城市边表示城市间的交通联系。 这个咨询系统可以回答旅客提出的各种问题。例如一位旅客要从 A 城到 B 城他希望选择一条中转次数最少的路线。假设图中每一站都需要换车则这个问题反映到图上就是找一条顶点 A 到顶点 B 所包含边的数目最少的路径。只需从顶点 A 出发对图做广度优先搜索一旦遇到顶点 B 就终止由此所得的广度优先生成树上从根顶点 A 到顶点 B 的路径就是中转次数最少的路径。
但是这只是一类最简单的图的最短路径问题。有时对于旅客来说可能更关心的是节省交通费用而对于司机来说里程和速度则是他们感兴趣的信息。为了在图上表示有关信息可对边赋予权权的值表示两城市间的距离或途中所需时间或交通费用等。此时路径长度的度量就不再是路径上边的数目而是路径上边的权值之和。考虑到交通图的有向性例如汽车的上山和下山轮船的顺水和逆水所花费的时间或代价就不相同所以交通网往往是用带权有向网表示。在带权有向网中习惯上称路径上的第一个顶点为源点Source最后一个顶点为终点Destination。
下面主要讨论两种最常见的最短路径问题一种是求从某个源点到其余各顶点的最短路径另一种是求每一对顶点之间的最短路径。 二、迪杰斯特拉算法
单源点的最短路径问题给定带权有向图 G 和源点 v0求从 v0 到 G 中其余各顶点的最短路径。
迪杰斯特拉Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法称为迪杰斯特拉算法。
(1) 迪杰斯特拉算法的求解过程
对于网 N (V, E)将 N 中的顶点分为两组
第一组 S已求出的最短路径的终点集合初始时只包含源点 v0。
第二组 V - S尚未求出的最短路径的顶点集合初始时为 V - {v0}。
算法将按各顶点与 v0 间最短路径长度递增的次序逐个将集合 V - S 中的顶点加入到集合 S 中去。在这个过程中总保持从 v0 到集合 S 中各顶点的路径长度始终不大于到集合 V - S 中各顶点的路径长度。
这种求解方法能确保是正确的因为假设 S 为已求得最短路径的终点的集合则可证明下一条最短路径设其终点为 x或是边 (v0, x)或是中间只是经过 S 中的顶点而最后到达顶点 x 的路径。
这可用反证法来证明。假设此路径上有一个顶点不在 S 中则说明存在一条终点不在 S 而长度比此路径短的路径。但是这是不可能的因为算法是按路径长度递增的次序来产生最短路径的故长度比此路径短的所有路径均已产生它们的终点必定在 S 中即假设不成立。
(2) 迪杰斯特拉算法的实现
假设用带权的邻接矩阵 arcs 来表示带权有向网 G。
算法的实现要引入以下辅助的数据结构 一维数组 S[i]记录从源点 v0 到终点 vi 是否已被确定最短路径长度true 表示确定false 表示尚未确定。 一维数组 Path[i]记录从源点 v0 到终点 vi 的当前最短路径上 vi 的直接前驱顶点序号。其初值为如果从 v0 到 vi 有弧则 Path[i] 为 v0否则为 -1。 一维数组 D[i]记录从源点 v0 到终点 vi 的当前最短路径长度。其初值为如果从 v0 到 vi 有弧则 D[i] 为弧上的权值否则为 。 最短路径为 D[k] Min{ D[i] | }求得从源点到 vk 的最短路径后将 vk 加入到第一组顶点集 S 中。 每当加入一个新的顶点到顶点集 S对第二组剩余的各个顶点而言多了一个 中转 顶点从而多了一个 中转 路径所以要对第二组剩余的各个顶点的最短路径长度进行更新。 原来从 v0 到 vi 的最短路径长度为 D[i]加入 vk 之和以 vk 作为中间顶点的 中转 路径长度为D[k] G.arcs[k][i]若 D[k] G.arcs[k][i] D[i]则用 D[k] G.arcs[k][i] D[i] 取代 D[i]。
AMGraph.h
#pragma once
typedef char VertexType;
typedef int ArcType;
#define DEFAULT_CAPACITY 2
typedef struct AMGraph
{VertexType* vertices;ArcType** arcs;int vSize;int aSize;int capacity;
}AMGraph;
void AMGraphInit(AMGraph* pg);
void ShowAdjMatrix(AMGraph* pg);
int GetVertexPos(AMGraph* pg, VertexType v);
void InsertVertex(AMGraph* pg, VertexType v);
void InsertArc(AMGraph* pg, VertexType v1, VertexType v2, ArcType cost);
// 迪杰斯特拉算法
void ShortestPath_DIJ(AMGraph* pg, VertexType v, int* D, int* Path);
AMGraph.c
#include AMGraph.h
#include assert.h
#include stdlib.h
#include stdio.h
#include stdbool.h
void AMGraphInit(AMGraph* pg)
{assert(pg);pg-vSize pg-aSize 0;pg-capacity DEFAULT_CAPACITY;
pg-vertices (VertexType*)malloc(sizeof(VertexType) * pg-capacity);assert(pg-vertices);
pg-arcs (ArcType**)malloc(sizeof(ArcType*) * pg-capacity);assert(pg-arcs);for (int i 0; i pg-capacity; i){pg-arcs[i] (ArcType*)malloc(sizeof(ArcType) * pg-capacity);assert(pg-arcs[i]);for (int j 0; j pg-capacity; j){if (i j)pg-arcs[i][j] 0;elsepg-arcs[i][j] INT_MAX;}}
}
void ShowAdjMatrix(AMGraph* pg)
{assert(pg);printf( ); // 输出 3 个空格for (int i 0; i pg-vSize; i){printf(%c , pg-vertices[i]);}printf(\n);
for (int i 0; i pg-vSize; i){printf(%c , pg-vertices[i]);for (int j 0; j pg-vSize; j){if (pg-arcs[i][j] INT_MAX)printf(# ); // 用 # 代替 ∞elseprintf(%-3d, pg-arcs[i][j]);}printf(\n);}
}
int GetVertexPos(AMGraph* pg, VertexType v)
{assert(pg);for (int i 0; i pg-vSize; i){if (pg-vertices[i] v)return i;}return -1;
}
void InsertVertex(AMGraph* pg, VertexType v)
{assert(pg);// 考虑是否需要扩容if (pg-vSize pg-capacity){VertexType* tmp1 (VertexType*)realloc(pg-vertices, sizeof(VertexType) * 2 * pg-capacity);assert(tmp1);pg-vertices tmp1;
ArcType** tmp2 (ArcType**)realloc(pg-arcs, sizeof(ArcType*) * 2 * pg-capacity);assert(tmp2);pg-arcs tmp2;for (int i 0; i pg-capacity; i){ArcType* tmp3 (ArcType*)realloc(pg-arcs[i], sizeof(ArcType) * 2 * pg-capacity);assert(tmp3);pg-arcs[i] tmp3;for (int j pg-capacity; j 2 * pg-capacity; j){pg-arcs[i][j] INT_MAX;}}for (int i pg-capacity; i 2 * pg-capacity; i){pg-arcs[i] (ArcType*)malloc(sizeof(ArcType) * 2 * pg-capacity);assert(pg-arcs[i]);for (int j 0; j 2 * pg-capacity; j){if (i j)pg-arcs[i][j] 0;elsepg-arcs[i][j] INT_MAX;}}
pg-capacity * 2;}// 插入顶点pg-vertices[pg-vSize] v;
}
void InsertArc(AMGraph* pg, VertexType v1, VertexType v2, ArcType cost)
{assert(pg);int pos1 GetVertexPos(pg, v1);int pos2 GetVertexPos(pg, v2);if (pos1 -1 || pos2 -1)return;
if (pg-arcs[pos1][pos2] ! INT_MAX)return;
pg-arcs[pos1][pos2] cost;pg-aSize;
}
// 迪杰斯特拉算法的实现
void ShortestPath_DIJ(AMGraph* pg, VertexType v, int* D, int* Path)
{assert(pg);int pos GetVertexPos(pg, v);if (pos -1)return;
bool* S (bool*)malloc(sizeof(bool) * pg-vSize);assert(S);for (int i 0; i pg-vSize; i){S[i] false;D[i] pg-arcs[pos][i];if (i ! pos D[i] ! INT_MAX)Path[i] pos;elsePath[i] -1; }S[pos] true;
for (int i 0; i pg-vSize - 1; i){int min;int k;int flag 1;for (int j 0; j pg-vSize; j){if (S[j] ! false){continue;}if (flag){min D[j];k j;flag 0;continue;}if (D[j] min){min D[j];k j;}}
S[k] true;for (int j 0; j pg-vSize; j){
if (S[j] false pg-arcs[k][j] ! INT_MAX D[k] pg-arcs[k][j] D[j]){D[j] D[k] pg-arcs[k][j];Path[j] k;}}}
free(S);
}
Test.c
#include AMGraph.h
#include stdio.h
#include stdlib.h
#include assert.h
int main()
{AMGraph g;AMGraphInit(g);InsertVertex(g, A);InsertVertex(g, B);InsertVertex(g, C);InsertVertex(g, D);InsertVertex(g, E);InsertVertex(g, F);InsertArc(g, A, C, 10);InsertArc(g, A, E, 30);InsertArc(g, A, F, 100);InsertArc(g, B, C, 5);InsertArc(g, C, D, 50);InsertArc(g, D, F, 10);InsertArc(g, E, D, 20);InsertArc(g, E, F, 60);ShowAdjMatrix(g);printf(\n);
int* D (int*)malloc(sizeof(int) * g.vSize);int* Path (int*)malloc(sizeof(int) * g.vSize);assert(D Path);ShortestPath_DIJ(g, A, D, Path);
for (int i 1; i g.vSize; i){if (D[i] INT_MAX)printf(从 A 到 %c 没有路径\n, g.vertices[i]);elseprintf(从 A 到 %c 的最短路径长度为%d\n, g.vertices[i], D[i]);}free(D);free(Path);return 0;
} 三、弗洛伊德算法
求解每一对顶点之间的最短路径有两种方法其一是分别以图中的每个顶点为源点共调用 n 次迪杰斯特拉算法其二是采用下面介绍的弗洛伊德Floyd算法。两种算法的时间复杂度均为 O(n^3)但后者形式上较简单。
弗洛伊德算法仍然使用带权的邻接矩阵 arcs 来表示有向网 G求从顶点 vi 到 vj 的最短路径。
算法的实现要引入以下辅助的数据结构 二维数组 D[i][j]记录顶点 vi 到 vj 之间的最短路径长度。 二维数组 Path[i][j]最短路径上顶点 vj 的前一顶点的序号。
算法步骤
将 vi 到 vj 的最短路径长度初始化即 D[i][j] G.arcs[i][j]然后进行 n 次比较和更新。 在 vi 和 vj 间加入顶点 v0比较 (vi, vj) 和 (vi, v0, vj) 的路径长度取其中较短者为 vi 到 vj 的中间顶点序号不大于 0 的最短路径。 在 vi 和 vj 间加入顶点 v1得到 (vi, ..., v1) 和 (v1, ..., vj)其中 (vi, ..., v1) 是 vi 到 v1 的且中间顶点序号不大于 0 的最短路径(v1, ..., vj) 是 v1 到 vj 的且中间顶点的序号不大于 0 的最短路径这两条路径已在上一步中求出。比较 (vi, ...., v1, ..., vj) 与上一步求出的 vi 到 vj 的中间顶点序号不大于 0 的最短路径取其中较短者作为 vi 到 vj 的中间顶点序号不大于 1 的最短路径。 依次类推在 vi 和 vj 间加入顶点 vk得到 (vi, ..., vk) 和 (vk, ..., vj)它们分别是从 vi 到 vk 和从 vk 到 vj 的中间顶点序号不大于 k - 1 的最短路径将 (vi, ..., vk, ..., vj) 和已经得到的从 vi 到 vj 且中间顶点序号不大于 k - 1 的最短路径相比较其长度较短者便是从 vi 到 vj 的中间顶点的序号不大于 k 的最短路径。这样经过 n 次比较后最后求得的必是从 vi 到 vj 的最短路径。按此方法可用同时求得各对顶点间的最短路径。
void ShortestPath_Floyd(AMGraph* pg, int** D, int** Path)
{assert(pg);for (int i 0; i pg-vSize; i){for (int j 0; j pg-vSize; j){D[i][j] pg-arcs[i][j];if (i ! j D[i][j] ! INT_MAX)Path[i][j] i;elsePath[i][j] -1;}}
for (int k 0; k pg-vSize; k){for (int i 0; i pg-vSize; i){for (int j 0; j pg-vSize; j){if (i ! k j ! k i ! j){if (D[i][k] ! INT_MAX D[k][j] ! INT_MAX D[i][k] D[k][j] D[i][j]){D[i][j] D[i][k] D[k][j];Path[i][j] Path[k][j];}}}}}
}
Test.c
#include AMGraph.h
#include stdio.h
#include stdlib.h
#include assert.h
int main()
{AMGraph g;AMGraphInit(g);InsertVertex(g, A);InsertVertex(g, B);InsertVertex(g, C);InsertVertex(g, D);InsertArc(g, A, B, 1);InsertArc(g, A, D, 4);InsertArc(g, B, C, 9);InsertArc(g, B, D, 2);InsertArc(g, C, A, 3);InsertArc(g, C, B, 5);InsertArc(g, C, D, 8);InsertArc(g, D, C, 6);ShowAdjMatrix(g);printf(\n);
int** D (int**)malloc(sizeof(int*) * g.vSize);assert(D);for (int i 0; i g.vSize; i){D[i] (int*)malloc(sizeof(int) * g.vSize);assert(D[i]);}int** Path (int**)malloc(sizeof(int*) * g.vSize);assert(Path);for (int i 0; i g.vSize; i){Path[i] (int*)malloc(sizeof(int) * g.vSize);assert(Path[i]);}ShortestPath_Floyd(g, D, Path);
for (int i 0; i g.vSize; i){for (int j 0; j g.vSize; j){printf(%d , D[i][j]);}printf(\n);}printf(\n);for (int i 0; i g.vSize; i){for (int j 0; j g.vSize; j){printf(%d , Path[i][j]);}printf(\n);}
free(D);free(Path);return 0;
}
