多源最短路径算法

多源最短路径算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

简单的来说，算法的主要思想是动态规划(dp)，而求最短路径需要不断松弛(熟悉spfa算法的可能熟悉松弛)。

而算法的具体思想为：

邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.

从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。

而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。

重复上述直到最后插点试探完成。

其中第三步的状态转移方程为:

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径.

对于程序而言，这个插入的过程相当简单。核心代码只有四行！

代码如下

#include

#include

using namespace std;

#define maxn 1000

int dist;

void floyd(int n)

{

for (int i = 1; i