floyd最短路径算法c

1. 求计算机求解关系R的传递闭包 C语言算法

传递闭包,最简单的技术是采用 【弗洛伊德算法】

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

Floyd-Warshall算法的原理是动态规划。

设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

代码请见：

2. Floyd算法是什么

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵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来记录两点间的最短路径。
采用的是(松弛技术)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3); 其状态转移方程如下： 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]这条路

3. 弗洛伊德算法求出最短距离

（1）利用二维数组dist[i][j]记录当前vi到vj的最短路径长度，数组dist的初值等于图的带权邻接矩阵;

（3）依次向S中加入v0,v1…vn-1，每加入一个顶点，对dist[i][j]进行一次修正：设S={v0,v1…vk-1}，加入vk，则dist(k)[i][j]=min{dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
dist(n-1)[i][j]就是vi到vj的最短路径长度。

弗洛伊德最短距离算法（FloydShortestPathAlgorithm）又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
中文名弗洛伊德最短距离算法
外文名FloydShortestPathAlgorithm
所属学科IT
所属领域程序设计
简介
最短路问题是网络最优化中一个基本而又非常重要的问题，这一问题相对比较简单，在实际生产和生活中经常遇到，许多的网络最优化问题可以化为最短路问题，或者用最短路算法作为其子程序.因此，最短路的用途已远远超出其表面意义迄今为止，所有最短路算法都只对不含负回路的网络有效，实际上对含有负回路的网络，其最短路问题是NP困难的，因此本研究所讨论的网络也不含负回路.此外，如果将无向图每条边用两条端点相同、方向相反的弧来代替，可以将其化为有向图，因而不讨论无向图.本研究中未述及的术语、记号。
Floyd算法是一种用于寻找给定加权图中顶点间最短路径的算法，以1978年图灵奖获得者斯坦福大学计算机科学系教授RobertW．Floyd命名。Floyd算法采用动态规划的原理计算两两顶点间最短路径，主要解决网络路由寻找最优路径的问题。