Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法

时间复杂度：O（n^3）

状态转移方程：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

有无向图如下 求各节点之间的最短路径

代码

#include<iostream>
#include<iomanip>
using namespace std;
int d[9][9];//d数组 存放每个顶点到每个顶点的最短路径长度
int p[9][9];//p数组 存放最短路径
int main(){
	//初始化数组
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++){
			d[i][j] = 0xfffffff;
			p[i][j] = j;
		}
	//向邻接矩阵中写入权值
	{
		d[0][0] = 0; d[0][1] = 1; d[0][2] = 5;
		d[1][0] = 1; d[1][1] = 0; d[1][2] = 3; d[1][3] = 7; d[1][4] = 5;
		d[2][0] = 5; d[2][1] = 3; d[2][2] = 0; d[2][4] = 1; d[2][5] = 7;
		d[3][1] = 7; d[3][3] = 0; d[3][4] = 2; d[3][6] = 3;
		d[4][1] = 5; d[4][2] = 1; d[4][3] = 2; d[4][4] = 0; d[4][5] = 3; d[4][6] = 6; d[4][7] = 9;
		d[5][2] = 7; d[5][4] = 3; d[5][5] = 0; d[5][7] = 5;
		d[6][3] = 3; d[6][4] = 6; d[6][6] = 0; d[6][7] = 2; d[6][8] = 7;
		d[7][4] = 9; d[7][5] = 5; d[7][6] = 2; d[7][7] = 0; d[7][8] = 4;
		d[8][6] = 7; d[8][7] = 4; d[8][8] = 0; 
	}
	//更新存放最短距离的d邻接矩阵  更新存放路径的p数组
	for (int k = 0; k < 9; k++)
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) {
				if (d[i][j] > d[i][k] + d[k][j]){
					d[i][j] = d[i][k] + d[k][j];
					p[i][j] = p[i][k];
				}
			}
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << setw(4)<< d[i][j];
		}
		cout << endl;
	}
	cout << endl;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout <<setw(4)<< p[i][j];
		}
		cout << endl;
	}
	system("pause");
	return 0;
}

运行结果

d数组：

p数组：

注：
p数组中 p[i][j]存放的是从节点i到节点j最短路径的前驱结点，
如
从结点0到结点8首先要经过p[0][8]结点1，
从结点1到结点8首先要经过p[1][8]结点2，
从结点2到结点7首先要经过p[2][8]结点4，
从结点4到结点7首先要经过p[4][8]结点3，
从结点3到结点7首先要经过p[3][8]结点6，
从结点6到结点7首先要经过p[6][8]结点7
从结点7到结点8首先要经过p[7][8]结点8，，
即：
结点0到结点8的最短路径为0 1 2 4 3 6 7 8
由图计算得到最短路径长度为16，对应存放最短路径长度的d数组中的p[0][8]=16