• 无向图的最短路径floyd算法实现，代码清晰。
• ## Floyd算法代码

千次阅读 2019-03-25 12:37:53
//Floyd-Warshall算法核心语句 for(k=1;k;k++) for(i=1;i;i++) for(j=1;j;j++) if(e[i][j]>e[i][k]+e[k][j] ) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i;i++) { for(j=1;j;j++) { ...
#include <stdio.h>
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//读入边
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd-Warshall算法核心语句
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
//输出最终的结果
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}



展开全文
• floyd算法代码 弗洛伊德·沃霍尔 (Floyd Warshall) The Floyd Warshall algorithm, itis the algorithm in which there is the use of different characterization of structure for a shortest path that we used ...
floyd算法代码 弗洛伊德·沃霍尔 (Floyd Warshall)
The Floyd Warshall algorithm, itis the algorithm in which there is the use of different characterization of structure for a shortest path that we used in the matrix multiplication which is based on all pair algorithms. The algorithm considers the intermediate vertices of the shortest path, where an intermediate vertex of a simple path p =< v1, v2, ..., VL> is any vertex of p other than v1 or VL, that is, a vertex in the set {v2, v3,..., vl-1}.
Floyd Warshall算法是一种算法，其中我们在基于所有对算法的矩阵乘法中使用了最短路径的不同结构表征。 该算法考虑最短路径的中间顶点，其中简单路径p = <v1，v2，...，VL>的中间顶点是除v1或VL以外的p的任何顶点，即设置{v2，v3，...，vl-1} 。
The Floyd Warshall algorithm is based on the following observation. Suppose the vertices of the G be V = {1, 2,..., n}, and assume a subset {1, 2, ..., k} of the vertices for some k. For any pair of vertices i, j £ v consider that all paths from i to j which have their intermediate vertices all drawn from {1, 2,..., k}, and now let p be the minimum weight path from among them. The relationship between path p and shortest paths from i to j with all intermediate vertices in a set {1, 2,..., k-1} is exploited by the Floyd Warshall algorithm.
Floyd Warshall算法基于以下观察。 假设G的顶点是V = {1，2，...，N}，并且假设顶点对某个k的子集{1，2，...，K}。 对于任何一对顶点i ， j£v都认为从i到j的所有路径的中间顶点都取自{1，2，...，k} ，现在令p是其中的最小权重路径。 Floyd Warshall算法利用路径p和从i到j的最短路径之间的所有中间顶点在集合{1,2，...，k-1}中的关系。
Let the weight of a shortest path from vertex i to the vertex j with all intermediate vertices in the set {1, 2, ..., k} be d (ij) ^ (k), when k = 0, a path from vertex i to vertex j with no intermediate vertex numbered higher than 0 has no intermediate vertices at all. It has at most one edge, hence (ij) ^ (0) = w (ij), A recursive definition is given by
设从顶点i到顶点j且集合{1，2，...，k}中所有中间顶点的最短路径的权重为d(ij)^(k) ，当k = 0时 ，从从顶点i到顶点j ，没有中间顶点的编号大于0，根本没有中间顶点。 它最多具有一个边，因此(ij)^(0)= w(ij) ，递归定义为
d (ij) ^ (k) ={ w (ij)      if k = 0
{Min (d (ij) ^ (k-1), d (ik) ^ (k-1) + d (kj) ^ (k-1)   if k >= 1

Floyd Warshall算法 (Floyd Warshall Algorithm)
    1.	n = rows [W]
2.	D ^ (0) = W
3.	For k = 1 to n
4.	Do for I = 1 to n
5.	Do for j = 1 to n
6.	d (ij) ^ (k) = min (d(ij) ^ (k-1), d (ik) ^ (k-1) + d(kj) ^ (k-1))
7.	return D ^ (n)

The running time of the Floyd Warshall algorithm is determined by the triply nested for loop of line 3 to 6. Each execution of the line 6 takes O (1) time. Thus the algorithm runs in O (n ^ 3) time.
Floyd Warshall算法的运行时间由第3行到第6行的循环的三重嵌套确定。第6行的每次执行花费O(1)时间。 因此，该算法运行时间为O(n ^ 3)。
In the Floyd Warshall algorithm, there are many ways for the constructing the shortest paths. One way is to compute the matrix D of the shortest path weights and then construct the predecessor matrix π from the matrix D. This method can be implemented to run in O (n ^ 3) time.
在Floyd Warshall算法中 ，有许多方法可以构造最短路径。 一种方法是计算最短路径权重的矩阵D，然后从矩阵D构造先前的矩阵π。可以将该方法实现为在O(n ^ 3)时间内运行。
Example:
例：
The sequence of matrices D ^ (k) and π ^ k (k computed by the Floyd Warshall algorithm) for given graph is computed as follows:
矩阵d ^(k)和π^ K(K 内由Floyd-Warshall算法计算的)对于给定的图形的序列被计算为如下：
References:
参考文献：
Introduction to Algorithms, 3rd Edition 算法简介，第3版 CHAPTER 26: ALL-PAIRS SHORTEST PATHS 第26章：全对最短路径 All-Pairs Shortest Paths 全对最短路径 翻译自: https://www.includehelp.com/algorithms/floyd-warshall-algorithm-with-its-pseudo-code.aspxfloyd算法代码
展开全文
• main.cpp #include<stdio.h>...#include"Floyd.h" void main() { printf("无向图\n"); MGraph Graph; Graph = BuildGraph(); Floyd(Graph,1); } Floyd.h #ifndef Dijkstra #define...
main.cpp
#include<stdio.h>
#include<stdlib.h>
#include"Floyd.h"

void main()
{
printf("无向图\n");
MGraph Graph;
Graph = BuildGraph();
Floyd(Graph,1);
}

Floyd.h
#ifndef Dijkstra

#define MaxVertexNum 100 //图的最大节点
#define INFINITY 0xFFFF

typedef int Vertex; //顶点下标
typedef int WeigthType; //边的权值
typedef int DataType; //顶点的数据类型

//边的定义
typedef struct ENode {
Vertex v1, v2;
WeigthType weigth;
}*PtrToENode;
typedef PtrToENode Edge;

//图的定义
typedef struct GNode {
int Nv; //顶点数量
int Ne; //边的数量
WeigthType G[MaxVertexNum][MaxVertexNum];//邻接矩阵,存边的权重
DataType Data[MaxVertexNum];//顶点的数据
}*PtrToGNode;
typedef PtrToGNode MGraph;

void InsertEdge(MGraph Graph, Edge E);
MGraph BuildGraph();
void Floyd(MGraph Graph, Vertex S);

#endif // !BFS
#pragma once


Floyd.cpp
#include"Floyd.h"
#include"stdlib.h"
#include"stdio.h"

int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];

//创建一个没有边的图
MGraph CreatGraph(int VertexNum)
{
Vertex V, W;
MGraph Graph;

Graph = (MGraph)malloc(sizeof(struct GNode));
if (!Graph)
{
printf("Graph生成失败");
exit(-1);
return NULL;
}
Graph->Nv = VertexNum;
Graph->Ne = 0;

for (V = 0; V < Graph->Nv; V++)
{
for (W = 0; W < Graph->Nv; W++)
{
Graph->G[V][W] = INFINITY;
}
}

return Graph;
}

//构建一个图
MGraph BuildGraph()
{
int Nv, i;
Vertex V;
Edge E;
MGraph Graph;

printf_s("请输入插入节点的个数\n");
scanf_s("%d", &Nv);

Graph = CreatGraph(Nv);

printf_s("请输入插入边的个数\n");
scanf_s("%d", &(Graph->Ne));
if (Graph->Ne != 0)
{
E = (Edge)malloc(sizeof(struct ENode));
if (!E)
{
printf("E生成失败");
exit(-1);
return NULL;
}
for (i = 0; i < Graph->Ne; i++)
{
printf("请输入第%d条边:  V1,V2,权重\n", i);
scanf_s("%d %d %d", &(E->v1), &(E->v2), &(E->weigth));
InsertEdge(Graph, E);
}
}

for (V = 0; V < Graph->Nv; V++)
{
printf("请输入第%d个顶点的数据\n", V);
scanf_s("%d", &(Graph->Data[V]));
}

return Graph;
}

void Visit(Vertex V)
{
printf("正在访问顶点%d\n", V);
}

bool IsEdge(MGraph Graph, Vertex V, Vertex W)
{
return Graph->G[V][W] < INFINITY ? true : false;
}

void Floyd(MGraph Graph, Vertex S)
{
Vertex i,j,k;
//初始化path和dist

for (i = 0;i < Graph->Nv;i++)
{
for ( j = 0; j < Graph->Nv; j++)
{
dist[i][j] = Graph->G[i][j];
path[i][j] = -1;
}
}

for ( k = 0; k < Graph->Nv; k++)
{
for (i = 0; i < Graph->Nv; i++)
{
for (j = 0; j < Graph->Nv; j++)
{
if (i == j)
{
continue;
}
if (dist[i][k] + dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];

if (dist[i][j] < 0)
{
exit(-1);//排除负值
}

path[i][j] = k;
}
}
}
}

for (i = 0; i < Graph->Nv; i++)
{
for (j = 0; j < Graph->Nv; j++)
{
printf("%d 到%d最小距离是 : %d\n", i, j,dist[i][j]);
}
}

printf("路径数组 :\n");

for (i = 0; i < Graph->Nv; i++)
{
for (j = 0; j < Graph->Nv; j++)
{
printf("%d\t", path[i][j]);
}
printf("\n");
}

}

//插入边
void InsertEdge(MGraph Graph, Edge E)
{
Graph->G[E->v1][E->v2] = E->weigth;
Graph->G[E->v2][E->v1] = E->weigth;
}




展开全文
• 一个号称只有5行代码算法， 由1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该算法有于求一个带权有向图(Wighted Directed Graph)的任意两点的最短距离的算法，运用了动态规划的思想, ...
一个号称只有5行代码的算法， 由1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该算法有于求一个带权有向图(Wighted Directed Graph)的任意两点的最短距离的算法，运用了动态规划的思想, 算法的时间复杂度为O(V^3)，空间复杂度O(V^2)。其核心思想是，在两个顶点之间插入一个或一个以上的中转点，比较经过与不经过中转点的距离哪个更短。同时，我们需要引入2个矩阵，一个邻接矩阵D，用来计算每个相邻点的距离，也就是我们的已知条件，第二个矩阵P，则用来表示中间点k的代数。比如说P中p[i,j]的值就是i与j两点的中间点代数。我们在进行Floyd算法的时候，也要像Dijkstra算法一样，不停的更新这两个矩阵。当我们根据一点规律变化中间点k的时候，也要遍历所有的最小距离和中间点，若D[i,j]<D[i,k]+D[j,k],则矩阵D中的distance[i,j]需要改变成D[i,k]+D[j,k]，矩阵P中的P[i,j]要改为k。在遍历掉所有点为中心之后，Floyd算法完成。这个中转点的思想，我们可以想象现实中的自ekd旅行驾游问题，有的城市间的道路好走，比如存在高速公路，其需要的时间就越短，有的城市间只有原始的泥泞小道，行驶时就很耗时间。比如A地直接到B地需要7小时A地经由C地再到B地，则要1+4=5小时A地经由C地再到D地再到B地，则要1+1+1小时。换言之，这类似动态规则的背包问题，从A地到B地，每个中转点可以选择也可以不选择，这个逻辑就是对应代码中的松弛操作。要求出所有地方（顶点）之间的最短距离，就需要n^3次松弛操作（三重循环）Floyd的核心5行代码：for需要注意的是，Floyd算法都是围绕顶点展开，因此其表示法只能选择相邻距阵。在相邻距阵中，我们默认所有顶点的权重是无限大，表示它们都不相邻，其实这在Floyd算法有点不对，因为顶点到它自身的距离应该为零，因此这个要改动一下。其完整实现如下：class 
展开全文
• package https://u.wechat.com/EJieeuarjuCJrgjvdHaaoKk (二维码自动识别)
• 引言在研究路径选择和流量分配等交通问题时，常常会用到最短路算法。用最短路算法解决交通问题存在两个难点：一、算法的选择和程序的编写。最短路算法有很多种改进算法和启发式...Floyd算法是一个经典的动态规划算法...
• for(k=0;k<n;k++)//中转站0~k for(i=0;i<n;i++) //i为起点 for(j=0;j<n;j++) //j为终点 if(d[i][j]>d[i][k]+d[k][j])//松弛操作 d[i][j]=d[i][k]+d[k][...
• floyd算法的C++代码，用的时候只要改几个参数就可以了
• Floyd算法与Dijstra的区别在于Floyd计算的是任意两点间的最短路径。 可以这样思考，首先是各点都不允许借路通过，然后依次从第一个点到最后一个点均允许借路通过，每次均取最短路，则到最后求得的就是各个点的最...
• 主要介绍了floyd算法实现思路及实例代码，有需要的朋友可以参考一下
• 利用Floyd算法以及Dijkstra算法解决选址问题以及matlab代码文档
• 写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵） 2.解析 面对上面这幅图，我们要做的是求出个顶点之间的最短距离。那么首先我们要做的讲就是将上面这幅图转化为一个二维矩阵，定义一个顶点到它自身...
• 写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵），按实验报告模板编写算法。 2.解析 （1）、 Floyd算法的核心思想是动态规划，它将多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个...
• ## floyd算法

千次阅读 2018-11-02 13:08:33
floyd算法解决的问题是在图中找到从i号结点到j号结点最短路径值（边的权值）的问题，核心代码就下面四行 for(int k = 0;k &lt; n;k++) for(int i = 0;i &lt; n;i++) for(int j = 0;j &lt; n;j++) dp...
• ## Floyd算法正确性

千次阅读 2016-01-10 17:21:25
Floyd算法是图论中求最短路径的一个算法，三层循环，就能获得任意起始点与终止点的最短路径，很简洁也很神奇，... Floyd算法代码如下： for(int k=0;i {    for(int i=0;i  {   for(int j=0;
• Floyd算法思想，准确详细的描述了算法的思想和方法，适合新手，并附有代码
•  首先是Floyd算法，这种算法思路是最简单的，但是相对于来说，时间复杂度就高一些，这种方法核心思想就是不断进行边松弛优化，主要代码如下; void Floyd(vector&lt;vector&lt;int&gt;&gt; &...
• Floyd算法(原理|代码实现) http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html 正如我们所知道的，Floyd算法用于求最短路径。Floyd算法可以说是Warshall算法的扩展，三个...

...