数据结构上机实现——弗洛伊德算法

前言

它的思想就是在两个端点之间不断加入新节点，然后路径判断是否更短。同样，注释已经很详细了，原理不做深究，请自行复习。

注：本文的实验案例都是清华大学严蔚敏老师数据结构视频中所讲解的案例，所以本类的文章是十分适合大家对课上知识加深认识的。测试案例和源代码将会在文末给出。

算法

本算法的存储结构为邻接矩阵，类型声明如下：

typedef struct _graph {int matrix[MAX][MAX];//二维数组表示的矩阵char vexs[MAX];//顶点集int vexnum;//顶点个数int edgnum;//边的个数
}Graph, *pGraph;//邻接矩阵的存储结构，用pGraph指针指向

下面是算法本体

void Floyd(Graph* gra) {//初始化int n = gra->vexnum;vector<vector<int>> dist(n, vector<int>(n));//存放两点之间的最短距离长度vector<vector<int>> path(n, vector<int>(n));//存放两点的路径信息，第一个是前驱for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dist[i][j] = gra->matrix[i][j];if (gra->matrix[i][j] != INF) {path[i][j] = i;}else {path[i][j] = -1;}}}for (int k = 0; k < n; k++) {//k是中间插入的元素for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] + dist[k][j] < dist[i][j]) {//从i经过k到j的一条路径，原先的路径要短dist[i][j] = dist[i][k] + dist[k][j];//更新路径长度path[i][j] = path[k][j];//更新前驱}}}}
}

上机须知

对应的邻接矩阵，*表示没有路径0 1 * 3* 0 1 *5 * 0 2* 4 * 0

在我给出的测试源码里需要输入以下内容，直接粘贴就可以

4
6
a
b
c
d
a b 1
b c 1
c a 5
c d 2
d b 4
a d 3

源码地址：点击这里