• floyed算法，计算最短路径的算法，输入矩阵，即可输出最短路径矩阵
• Floyed 算法： import java.util.Arrays; public class Floyed { public static int[][] floyed(int[][] graph){ int[][] path=new int[graph.length][graph[0].length]; for(int i=0;i;i++){
Floyed 算法：
import java.util.Arrays;

public class Floyed {

public static int[][] floyed(int[][] graph){
int[][] path=new int[graph.length][graph[0].length];
for(int i=0;i<path.length;i++){
for(int j=0;j<path[0].length;j++){
if(graph[i][j]==Integer.MAX_VALUE) path[i][j]=-1;
//else path[i][j]=j;//从前往后找
else path[i][j]=i;//从后往前找
}
}
for(int k=0;k<graph.length;k++){
for(int i=0;i<graph.length;i++){
for(int j=0;j<graph.length;j++){
if(graph[i][k]==Integer.MAX_VALUE||graph[k][j]==Integer.MAX_VALUE){
continue;
}
if(graph[i][k]+graph[k][j]<graph[i][j]){
graph[i][j]=graph[i][k]+graph[k][j];
//path[i][j]=k;//这种写法是不对的，因为这只能说明从i到j经过k，k不一定是i的直接后继 如路径[0,3,4,2,5] 则k可能是4，这只与比较顺序有关系
path[i][j]=path[k][j];  //path[i][j]=path[k][j];是记录前驱位置，与else path[i][j]=i;对应
}
}
}
}
return path;
}
public static int[][] floyed2(int[][] graph){
int[][] path=new int[graph.length][graph[0].length];
for(int i=0;i<path.length;i++){
for(int j=0;j<path[0].length;j++){
if(graph[i][j]==Integer.MAX_VALUE) path[i][j]=-1;
else path[i][j]=j;//从前往后找
//else path[i][j]=i;//从后往前找
}
}
for(int k=0;k<graph.length;k++){
for(int i=0;i<graph.length;i++){
for(int j=0;j<graph.length;j++){
if(graph[i][k]==Integer.MAX_VALUE||graph[k][j]==Integer.MAX_VALUE){
continue;
}
if(graph[i][k]+graph[k][j]<graph[i][j]){
graph[i][j]=graph[i][k]+graph[k][j];
path[i][j]=path[i][k];//这种记录路径的方法很重要  path[i][j]=k 是记录后继位置 ,与else path[i][j]=j;对应
//path[i][j]=path[k][j];  //path[i][j]=path[k][j];是记录前驱位置，与else path[i][j]=i;对应
}
}
}
}
return path;
}
static final int max=Integer.MAX_VALUE;
public static void main(String[] args) {
int[][] graph={
{0,2,6,4},
{max,0,3,max},
{7,max,0,1},
{5,max,12,0}
};
int[][] path=floyed2(graph);
for(int i=0;i<graph.length;i++){
System.out.println(Arrays.toString(graph[i]));
}
for(int i=0;i<path.length;i++){
System.out.println(Arrays.toString(path[i]));
}

}
}

展开全文
• 这一讲简单介绍一下Floyed算法。 话不多说，先放一道题帮助理解（其实是懒得描述具体应用场景）。 Frogger Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is ...
这一讲简单介绍一下Floyed算法。
话不多说，先放一道题帮助理解（其实是懒得描述具体应用场景）。
Frogger

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.


Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying “Scenario #x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input

2
0 0
3 4

3
17 4
19 4
18 5

0


Sample Output

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414


严格来说，这并不是一道标准的Floyed题，题意是：在所有通路中，找到每一条通路中的最大距离，在这所有的距离中，找到一个最小值。
之所以也放到这里，首先是因为Floyed算法标志性的三重循环，其次也是想借此拓展一下该算法灵活的应用方式


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define maxsize 1010
#define inf 99999999
int x[maxsize],y[maxsize],sum=1;
double dis[maxsize][maxsize];//用来记录任意两点通路的单步最大长度

//计算两点间的距离
double caldistance(int x1,int y1,int x2,int y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main()
{
int m;
while(scanf("%d",&m)!=EOF)
{
if(m==0)
{
break;
}
int i,j,k;

//输入每个点的坐标
for(i=1;i<=m;i++)
{
scanf("%d %d",&x[i],&y[i]);
}

//计算任意两个点间的距离
for(i=1;i<=m;i++)
{
for(j=i;j<=m;j++)
{
if(j==i) dis[i][j]=0;
else
dis[i][j]=dis[j][i]=caldistance(x[i],y[i],x[j],y[j]);
}
}
//算法标志性的三重循环
//特别暴力的找到所有情况然后更新
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
{
for(k=1;k<=m;k++)
{
if(dis[j][k]>max(dis[j][i],dis[i][k]))
{
dis[j][k]=max(dis[j][i],dis[i][k]);
//注意i，j,k的顺序和位置，最初写错了，怎么都找不到问题错在哪里，一定要注意，
//如果是找最短路径的正宗Floyed，比较的就是dis[j][k]和dis[j][i]+dis[i][k]的大小，取小的那个
}

}
}
}

printf("Scenario #%d\nFrog Distance = %.3f\n\n", sum++, dis[1][2]);
}
return 0;
}



这个题巧妙的一点改动就实现了功能的“巨大”改变。

算法的核心就是那个三重循环及其嵌套顺序。
展开全文
• ## floyed算法

千次阅读 2015-09-05 09:47:10
/** floyed 是用动态规划解决完全最短路的算法，一次调用... floyed算法还可解决传递闭包，判断图是否为连通图 在解题时候一般不会只考 floyed 而是利用floyed 得到的结果，进行下一步解题 就像二分算法一样，提一
/**
floyed 是用动态规划解决完全最短路的算法，一次调用即可得到任意两个点间的最短路径
复杂度为O(n^3),适用于稠密图，顶点数一般在100 以内适用

结构简单，易于编写

floyed算法还可解决传递闭包，判断图是否为连通图

在解题时候一般不会只考 floyed 而是利用floyed 得到的结果，进行下一步解题
就像二分算法一样，提一下竞赛必考二分枚举
*/

const int inf = 0x3f3f3f3f;
const int M = 100;

int map[M][M]; //初始化map[][] = inf;

void addEdge(int u, int v, int w) {
map[u][v] = w;
map[v][u] = w; //floyed 也可以解决有向图
}

void floyed(int nv) {
int i, j, k;
for (i=1; i<=nv; i++)
for (j=1; j<=nv; j++)
for (k=1; k<=nv; k++)
map[i][j] = min(map[i][j], map[i][k]+map[k][j]);

}

/**
注意：连接矩阵添边都应该注意是否有重边，floyed 算法既可以解决有向图又可以解决
无向图，但是不能解决带负权回路的图
*/

收藏于 2011-11-18
来自于百度空间

展开全文
• FLOYD算法
FLOYD算法

​   这个算法我看了很久都没有看懂，最后突然茅塞顿开，感觉自己智商喂狗了。

​   最近天天搞一些花里胡哨的东西搞得心态爆炸，学起东西来特别慢，现在电脑已经装好了，感觉是时候开始认真准备acm了。

​   算法其实非常简单，dis[i][j][k] = max(dis[i][k][k-1] + dis[k][j][k-1], dis[i][j][k-1]);然后解释一下这里面的k，k不仅仅代表着从i到j可以借助k，还代表着从i到j可以借助0~k这k+1个点，也就是说，当k取到n-1的时候，就是所有的点都可以借助（也就是怎么走都没有问题）。

​   然后观察到方程前面是k后面只有k-1，所以可以优化一下空间变成dis[i][j] = max(dis[i][j], dis[i][k] + dis[k][j]);

这边贴一个带路径的Floyd：(题目：先输入一个小于100的正整数n，然后的n行输入图的邻接矩阵（10000表示无穷大，即两点之间没有边），之后再输入一个小于100的正整数m，最后的m行每行输入两个不同的0到n-1之间的整数表示两个点，用弗洛伊德算法求任意两点间的最短路径，并输出这些两个点之间的最短路径）

#include <iostream>

using namespace std;

int a[200][200] = { 0 };
int path[200][200] = { 0 };

int min(int a, int b) {
return a < b ? a : b;
}

void put(int x, int y) {
if (path[x][y] == -1)
return;
put(x, path[x][y]);
cout << path[x][y] << endl;
put(path[x][y], y);
}

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
memset(path, -1, sizeof(path));

for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j] > a[i][k] + a[k][j]) {
path[i][j] = k;
a[i][j] = a[i][k] + a[k][j];
}

int m, x, y;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> x >> y;
cout << x << endl;
put(x, y);
cout << y << endl;
}

return 0;
}

展开全文
• 利用Floyed算法计算网络中节点的最短距离，再计算网络效率。
• Floyed算法 最短路径-Dijkstra算法和Floyed算法 最短路径之Dijkstra算法和Floyed算法 哈哈，他山之石，可以攻玉 自己有心得，慢慢补充 转载于:https://www.cnblogs.com/celineccoding/p/4293563.html...
• bellom floyed 算法 //检测是否有负权回路 #include<cstdio> #include<iostream> #include<math.h> #include<algorithm> #include<cstring> using namespace std; int main() { ...
• 转自gzr的博客：https://www.cnblogs.com/TFLS-gzr/p/10381849.html，https://www.cnblogs.com/TFLS-gzr/p/10387463.html 感觉这是我目前浏览找到的最短路问题讲解...1 floyed算法 1）明确思想及功效：在图中求最...
• 思想讲解：Floyed算法变形：应用场景【例1】最短路径问题 Floyed-Warshall算法 O(N3) 简称Floyed(弗洛伊德)算法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3)，适用...
• Floyed算法求最短路径 ——HM Floyed是一个最短路径问题的一种较为简单的算法，既然简单，缺点就很多，如存储方式只能用二维邻接矩阵来完成...
• 在某些应用中，需要计算两个节点之间的最短路径，比较有名的是Dijkstra算法和floyed算法，都是基于节点的邻接关系求解任意两点直接的可达性和最短可达路径。 Dijkstra算法比较容易理解，无论是广度优先还是深度优先...
• 图 -Floyed算法 -Dijkstra算法 -拓扑排序算法
• 最短路径算法 给定一个有向图或无向图 G(V，E) 有时我们需要求...设图 G(V，E)（有向无向都无所谓，Floyed算法不关心，下面Dijkstra同） 用邻接矩阵来保存。设dis[i][j] 为结点 i 与结点 j 之间的距离，如果i与j之间
• Floyed算法是典型的暴力搜索，不过用到了动态规划的思想，整体的使用过程是，我们会考虑中间点的作用，简单的说，对于任何一个点i到j我们考虑下是i直接到j短还是i先到k再到j短，哪个短选哪个，所以我们在使用的时候...
• （一）Floyed算法是解决赋权图最短路问题的.（二）算法的基本思想：　利用图论中的传递关系，更新任意两点间的最短距离。（三）时间复杂度高。（四）算法的核心代码 1 for(k=1;k<=n;k++) 2 for(i=1;i<=n;i...
• 最短路径在数据结构的教材上有两种生成算法：Floyed算法和Dijkstra算法 Floyed算法 算法思想： 　通过三个for循环，求出各个点距离其他各个点的最短距离。其中，最外层for循环遍历中间节点k，第二第三层循环起点i...
• Floyed算法 最短路径 #include<iostream>#include<cstdio>int v,e,n; //v是顶点数，e是条数int v1[101][101],path[101][101]; using namespace std; void input(int n){ ...
• Floyed算法 Floyed-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 注意单独一条边的路径也不一定是最佳路径。 时间复杂度O(n^3),只要有存下...
• Floyed算法  此算法由Robert W. Floyd（罗伯特·弗洛伊德）于1962年发表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍尔）也独立发表了这个算法。Robert W．Floyd这个牛人是朵奇葩，他...
• 洛谷 P1119 灾后重建 理解Floyed算法 题解： 要理解Floyed算法的原理，每次取前k个点作为中转，不断更新。 不能硬背模板。 代码如下： #include<iostream> #include<algorithm> #include<stdio.h>...

...