最短路径(Floyd算法）(c/c++)

如果要得到图中各个顶点之间的最短路径，方法1：可以对每一个顶点采用Dijkstra算法；方法2：可以采用Floyd算法，它是一种用来求双源点之间最短路径的算法，采用邻接矩阵来存储图

辅助结构

int D[maxSize][maxSize];//表示从各个顶点之间最短路径长度

例：D[i][j]:表示从i顶点到j顶点的最短路径长度

bool p[maxSize][maxSize][maxSize];//表示最短路径上的结点 p[i][j][u] = true;//u顶点存在于从i到j最短路径上

简单示例

输入为下图：

一二三四

∞

4

11

∞

4

11

∞

4

6

∞

4

6

D

6

∞

2

6

∞

2

6

∞

2

5

∞

2

3

∞

∞

3

7

∞

3

7

∞

3

7

∞

\

AB

AC

\

AB

AC

\

AB

ABC

\

AB

ABC

p

BA

\

BC

BA

\

BC

BA

\

BC

BCA

\

BC

CA

CB

\

CA

CAB

\

CA

CAB

\

CA

CAB

\

一：初始的D数组为各点之间的权值，p表示各点之间最短路径所包含的结点
二：加入A点为各点之间的中转点，对两个数组进行更替，用黄色字体标出
三：加入B点…
四：加入C点…
当所有点都被做为过中转点，算法结束

Floyd算法

void floyd(mGraph& G) {int i, j, u;//初始化for (i = 0; i < G.vexnum; ++i)for (j = 0; j < G.vexnum; ++j){D[i][j] = G.arc[i][j];for (u = 0; u < G.vexnum; ++u)p[i][j][u] = false;if (D[i][j] < infini)p[i][j][i] = p[i][j][j] = true;}//更新数组，存储路径for (u = 0; u < G.vexnum; ++u)for (i = 0; i < G.vexnum; ++i)for (j = 0; j < G.vexnum; ++j)if (i!=j&&D[i][u] + D[u][j] < D[i][j])//对每个结点对加入u结点进行判断{D[i][j] = D[i][u] + D[u][j];for (int v = 0; v < G.vexnum; ++v)p[i][j][v] = p[i][u][v] || p[u][j][v];} }

完整示例

将上面的图作为输入：

#include<iostream> #define infini INT_MAX/3//最大值不选取INT_MAX，是防止溢出 #define maxSize 3//顶点数目 #define MAX 5//边的个数 //邻接矩阵 typedef struct {int vexnum, arcnum;//顶点数和边数char vex[maxSize];//顶点信息(字符)int arc[maxSize][maxSize];//二维数组(存储边上的信息) }mGraph;bool p[maxSize][maxSize][maxSize];//表示最短路径上的结点 int D[maxSize][maxSize];//表示从各个顶点之间最短路径长度void floyd(mGraph& G);//求最短路径 int main() {using namespace std;mGraph G;//邻接矩阵存储图并进行初始化G.vexnum = maxSize;G.arcnum = MAX;char vexData[maxSize] = { 'a', 'b', 'c'};//顶点信息int arcData[MAX][3] = { { 0, 1 ,4}, { 0, 2,11 }, { 1, 0 ,6}, { 1, 2,2 }, { 2, 0 ,3} };//连接的边int i, j;for (i = 0; i < G.vexnum; ++i){G.vex[i] = vexData[i];for (j = 0; j < G.vexnum; j++)G.arc[i][j] = infini;}for (i = 0; i < G.arcnum; i++)G.arc[arcData[i][0]][arcData[i][1]] = arcData[i][2];//初始化完毕cout << "求各点间最短路径: ";cout << endl;floyd(G);int c;for (i = 0; i < G.vexnum; ++i)for (j = 0; j < G.vexnum; ++j){if (D[i][j] == infini){cout << "不存在" << vexData[i] << "到" << vexData[j]<< "的路径" << endl;continue;}cout << vexData[i] << "到" << vexData[j]<< "的路径长度为：" << D[i][j] << " 包含顶点：";for (c = 0; c < G.vexnum; ++c)if (p[i][j][c] == true)cout << vexData[c] << ' ';cout << endl;}cout << endl;return 0; } void floyd(mGraph& G) {int i, j, u;//初始化for (i = 0; i < G.vexnum; ++i)for (j = 0; j < G.vexnum; ++j){D[i][j] = G.arc[i][j];for (u = 0; u < G.vexnum; ++u)p[i][j][u] = false;if (D[i][j] < infini)p[i][j][i] = p[i][j][j] = true;}//更新数组，存储路径for (u = 0; u < G.vexnum; ++u)for (i = 0; i < G.vexnum; ++i)for (j = 0; j < G.vexnum; ++j)if (i!=j&&D[i][u] + D[u][j] < D[i][j])//对每个结点对加入u结点进行判断{D[i][j] = D[i][u] + D[u][j];for (int v = 0; v < G.vexnum; ++v)p[i][j][v] = p[i][u][v] || p[u][j][v];} }

程序的输出结果为：

Dijkstra算法求最短路径：
https://blog.csdn.net/Little_ant_/article/details/104291049
（ps：希望大家可以多多点赞👍)

总结

以上是生活随笔为你收集整理的最短路径(Floyd算法）(c/c++)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。