floyd算法介绍 floyd算法是什么

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

2、在计算机科学中，Floyd-Warshall算法是一种在具有正或负边缘权重（但没有负周期）的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度（加权）。 虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径。 该算法的版本也可用于查找关系R的传递闭包，或（与Schulze投票系统相关）在加权图中所有顶点对之间的最宽路径。

3、Floyd-Warshall算法是动态规划的一个例子，并在1962年由Robert Floyd以其当前公认的形式出版。然而，它基本上与Bernard Roy在1959年先前发表的算法和1962年的Stephen Warshall中找到图形的传递闭包基本相同，并且与Kleene的算法密切相关 在1956年）用于将确定性有限自动机转换为正则表达式。算法作为三个嵌套for循环的现代公式首先由Peter Ingerman在1962年描述。

4、该算法也称为Floyd算法，Roy-Warshall算法，Roy-Floyd算法或WFI算法。

这是由其算法本身所决定的，其每一步求出任意一对顶点之间仅通过中间节点1,2,,k的最短距离，当1,2,,k扩展到所有顶点时，算法解出任意一对顶点间的最短距离，故顺序自然是：

for(k=1;k<n;++k)

//枚举任意一对顶点

由其状态转移方程来看，这个算法的顺序也很清晰，应该是先计算较小的k时任意ij之间的最短距离：

dij(k) = wij 如果k=0

min(dij(k-1),dik(k-1)+dkj(k-1)) 如果k>=1

其中i,j表示点对，k表示第1,2,,k时的最短路径

#include<stdioh>

#include<stringh>

int path[101][101]={0};

void p(int e,int s)

{

int k=path[e][s];

if(k!=0)

{

p(e,k);

printf(" %d",k);

p(k,s);

}

}

int main()

{

memset(path,0,sizeof(path));

int adj[101][101];

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

scanf("%d",&adj[i][j]);

if(adj[i][j]==0) adj[i][j]=65535;

}

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

if(k!=i)

for(int j=1;j<=n;j++)

if(j!=i && j!=k)

{

if(adj[i][k]+adj[k][j]<adj[i][j])

{

adj[i][j]=adj[i][k]+adj[k][j];

path[i][j]=k;

}

}

int s,e;

scanf("%d%d",&s,&e);

if(adj[s][e]==65535)

printf("No way!!\n");

else

{

printf("%d\n",adj[s][e]);

printf("%d",s);

p(s,e);

printf(" %d\n",e);

}

return 0;

}

/

著名的floyd算法，它是多源最短路径算法，也就说可以给除任意两结点的最短路，

如果它们有路，时间复杂度O(n^3)算法分析：

先提出疑问，这个算法是怎样做到求最短路径的呢？

其实对于最短路，我们说的路最短也就是是权值最小，并不是单方面的说路的长度

这个权值可以是造价，耗费，长度，时间等等，我们首先要理解这一点。

从小张家到小李家有50米的路程，到小王家有10米，小王家到小李家20米远，这时我们

要从小张家到王家最少要走多远，答案是30米，我们选择路线的时候没有直接走过去，而且发现

了一中转点，可以使得整个路程更短。其实floyd就用了这种思想，第一个循环枚举了用哪个

点来作为中转，第二第三循环枚举从谁走到谁，通过枚举所有的情况，最后就会得到最小值。

这时你会想，一个最短路是看整体的整个图来确定的，为什么每次两个点就可以搞定呢？

其实是这样的，每个使用过的点，在前一阶段求出了一个值，这时候再用它就等于已经继承了

它前面所计算出来的最短路的值，同过这个最短值上再去选择一条路，然后新形成的路还是一条

最短路，只是起终点不一样罢了。

这个算法抽象度较高，需加以图解和多想，掌握这个算法比较重要，它的思想在以后的

图论学习中比较重要，特别是继承的这种思想和松弛技术。

/

Floyd算法是一种用于在已知给定的加权图中求多源点之间最短路径的算法。它于Diskstra算法类似，不同点在于Diskstra计算的是单源点之间的最短路径。Floyd算法是在数学建模领域和日常工作中使用频率较高的路径分析算法。

Floyd作为一种典型的求多源最短路径问题的算法，是解决任意两个点之间最短路径的算法，它的思想是基于动态规划的思想。

见——第一章 算法基础——基础算法分析类型。

Floyd的核心思想也是基于动态规划的理论，过程也比较简单。

设 表示为i点到j点过程中以(1…k)集合中的节点为中间节点的最短路径长度，则：

（1）若最短路径经过点k，则 = + ;

（2）若最短路径不经过点k，则 = 。

于是 =

Floyd算法的时间复杂度为 ，空间复杂度为 。

不能编译运行的说法是错误，但是结果是否正确，我就不知道了，我不懂这个算法

public class FLOYD {

int[][] length = null;// 任意两点之间路径长度

int[][][] path = null;// 任意两点之间的路径

public FLOYD(int[][] G) {

int MAX = 100;

int row = Glength;// 图G的行数

int[][] spot = new int[row][row];// 定义任意两点之间经过的点

int[] onePath = new int[row];// 记录一条路径

length = new int[row][row];

path = new int[row][row][];

for (int i = 0; i < row; i++)

// 处理图两点之间的路径

for (int j = 0; j < row; j++) {

if (G[i][j] == 0)

G[i][j] = MAX;// 没有路径的两个点之间的路径为默认最大

if (i == j)

G[i][j] = 0;// 本身的路径长度为0

}

for (int i = 0; i < row; i++)

// 初始化为任意两点之间没有路径

for (int j = 0; j < row; j++)

spot[i][j] = -1;

for (int i = 0; i < row; i++)

// 假设任意两点之间的没有路径

onePath[i] = -1;

for (int v = 0; v < row; ++v)

for (int w = 0; w < row; ++w)

length[v][w] = G[v][w];

for (int u = 0; u < row; ++u)

for (int v = 0; v < row; ++v)

for (int w = 0; w < row; ++w)

if (length[v][w] > length[v][u] + length[u][w]) {

length[v][w] = length[v][u] + length[u][w];// 如果存在更短路径则取更短路径

spot[v][w] = u;// 把经过的点加入

}

for (int i = 0; i < row; i++) {// 求出所有的路径

int[] point = new int[1];

for (int j = 0; j < row; j++) {

point[0] = 0;

onePath[point[0]++] = i;

outputPath(spot, i, j, onePath, point);

path[i][j] = new int[point[0]];

for (int s = 0; s < point[0]; s++)

path[i][j][s] = onePath[s];

}

}

}

void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {// 输出i//

// 到j//

// 的路径的实际代码，point[]记录一条路径的长度

if (i == j)

return;

if (spot[i][j] == -1)

onePath[point[0]++] = j;

// Systemoutprint(" "+j+" ");

else {

outputPath(spot, i, spot[i][j], onePath, point);

outputPath(spot, spot[i][j], j, onePath, point);

}

}

public static void main(String[] args) {

int data[][] = {

{ 0, 27, 44, 17, 11, 27, 42, 0, 0, 0, 20, 25, 21, 21, 18, 27, 0 },// x1

{ 27, 0, 31, 27, 49, 0, 0, 0, 0, 0, 0, 0, 52, 21, 41, 0, 0 },// 1

{ 44, 31, 0, 19, 0, 27, 32, 0, 0, 0, 47, 0, 0, 0, 32, 0, 0 },// 2

{ 17, 27, 19, 0, 14, 0, 0, 0, 0, 0, 30, 0, 0, 0, 31, 0, 0 },// 3

{ 11, 49, 0, 14, 0, 13, 20, 0, 0, 28, 15, 0, 0, 0, 15, 25, 30 },// 4

{ 27, 0, 27, 0, 13, 0, 9, 21, 0, 26, 26, 0, 0, 0, 28, 29, 0 },// 5

{ 42, 0, 32, 0, 20, 9, 0, 13, 0, 32, 0, 0, 0, 0, 0, 33, 0 },// 6

{ 0, 0, 0, 0, 0, 21, 13, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0 },// 7

{ 0, 0, 0, 0, 0, 0, 0, 19, 0, 11, 20, 0, 0, 0, 0, 33, 21 },// 8

{ 0, 0, 0, 0, 28, 26, 32, 0, 11, 0, 10, 20, 0, 0, 29, 14, 13 },// 9

{ 20, 0, 47, 30, 15, 26, 0, 0, 20, 10, 0, 18, 0, 0, 14, 9, 20 },// 10

{ 25, 0, 0, 0, 0, 0, 0, 0, 0, 20, 18, 0, 23, 0, 0, 14, 0 },// 11

{ 21, 52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 0, 27, 22, 0, 0 },// 12

{ 21, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0 },// 13

{ 18, 41, 32, 31, 15, 28, 0, 0, 0, 29, 14, 0, 22, 0, 0, 11, 0 },// 14

{ 27, 0, 0, 0, 25, 29, 33, 0, 33, 14, 9, 14, 0, 0, 11, 0, 9 },// 15

{ 0, 0, 0, 0, 30, 0, 0, 0, 21, 13, 20, 0, 0, 0, 0, 9, 0 } // 16

};

for (int i = 0; i < datalength; i++)

for (int j = i; j < datalength; j++)

if (data[i][j] != data[j][i])

return;

FLOYD test = new FLOYD(data);

for (int i = 0; i < datalength; i++)

for (int j = i; j < data[i]length; j++) {

Systemoutprintln();

Systemoutprint("From " + i + " to " + j + " path is: ");

for (int k = 0; k < testpath[i][j]length; k++)

Systemoutprint(testpath[i][j][k] + " ");

Systemoutprintln();

Systemoutprintln("From " + i + " to " + j + " length :"

+ testlength[i][j]);

}

}

}

以上就是关于floyd算法介绍 floyd算法是什么全部的内容，包括:floyd算法介绍 floyd算法是什么、floyd算法、求一C# floyd算法代码等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！