算法思路
路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)，以此类推。最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
状态转移方程
其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。
核心算法
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
时间复杂度与空间复杂度
时间复杂度：因为核心算法是采用松弛法的三个for循环，因此时间复杂度为O（n^3）
空间复杂度：整个算法空间消耗是一个n*n的矩阵，因此其空间复杂度为O（n^2）
C++代码
// floyd.cpp : Defines the entry point for the console application.//
#include "stdafx.h"#include"iostream"#include"fstream"#define maxlen 20#define maximum 100using namespace std;
typedef struct graph{int vertex;int edge;int matrix[maxlen][maxlen];};int _tmain(int argc, _TCHAR* argv[]){ofstream outwrite;outwrite.open("h.txt",ios::app|ios::out);outwrite<<"welcome to the graph world!\n";outwrite<<"the initial matrix is:\n";int vertexnumber;int edgenumber;int beginning,ending,weight;int mindistance[maxlen][maxlen];int interval[maxlen][maxlen];graph floydgraph;cout<<"welcome to the graph world!"<<endl;cout<<"input the number of the vertex: ";cin>>vertexnumber;cout<<"input the number of the edge: ";cin>>edgenumber;for (int i = 0; i < vertexnumber; i++){ for (int j = 0; j < vertexnumber; j++) { floydgraph.matrix[i][j]=maximum; }}for (int i = 0; i <edgenumber; i++){ cout<<"please input the beginning index: "; cin>>beginning; cout<<"please input the ending index: "; cin>>ending; cout<<"please input the distance of the two dot: "; cin>>weight; floydgraph.matrix[beginning][ending]=weight;}for (int i = 0; i <vertexnumber; i++){ for (int j = 0; j < vertexnumber; j++) { mindistance[i][j]=floydgraph.matrix[i][j]; outwrite<<floydgraph.matrix[i][j]<<"\t"; interval[i][j]=-1; } outwrite<<"\n";}for (int k = 0; k <vertexnumber; k++){ for (int i = 0; i < vertexnumber; i++) { for (int j = 0; j < vertexnumber; j++) { if(mindistance[i][j]>mindistance[i][k]+mindistance[k][j]) { mindistance[i][j]=mindistance[i][k]+mindistance[k][j]; interval[i][j]=k; } } }}outwrite<<"\n"<<"after the floyd transition, the matrix is: "<<"\n";for (int i = 0; i < vertexnumber; i++){ for (int j = 0; j < vertexnumber; j++) { cout<<"the mindistance between "<<i<<" and "<<j <<" is: "; cout<<mindistance[i][j]<<endl; cout<<"the two points pass through the point: "<<interval[i][j]; cout<<endl; outwrite<<mindistance[i][j]<<"\t"; } outwrite<<"\n";}outwrite<<"\n";outwrite<<"the points between the beginning point and the ending point is:"<<"\n";for (int i = 0; i < vertexnumber; i++){ for (int j = 0; j < vertexnumber; j++) { outwrite<<interval[i][j]<<"\t"; } outwrite<<"\n";}outwrite.close();getchar();getchar();getchar();return 0;}
本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2016-11/137537.htm
以上就上有关floyd算法学习笔记的相关介绍，要了解更多floyd算法,floyd算法学习笔记,编程,Linux编程,Linux Shell,Android,Android教程,JAVA,C语言,Python,HTML5内容请登录学步园。