/*
证明next[i][j] = k;是错误的例子
Node 0 Position (4,61) nextJump -1 Neighbor [3] goodNeighbor [3]
Node 1 Position (89,19) nextJump 1 Neighbor [4, 2] goodNeighbor [4, 2]
Node 2 Position (88,74) nextJump 2 Neighbor [4, 1] goodNeighbor [4, 1]
Node 3 Position (23,85) nextJump 3 Neighbor [4, 0] goodNeighbor [4, 0]
Node 4 Position (68,59) nextJump 3 Neighbor [2, 1, 3] goodNeighbor [2, 1, 3]
*/
#include "iostream"
#include "vector"
using namespace std;
vector<int> path;
int min(int a,int b)
{
return a>b?b:a;
}
/*
int cost[10][10]=
{
0, 99, 8, 7, 6, 5, 4, 3, 2, 1,
99, 0, 99, 8, 7, 6, 5, 4, 3, 2,
8, 99, 0, 99, 8, 7, 6, 5, 4, 3,
7, 8, 99, 0, 99, 8, 7, 6, 5, 4,
6, 7, 8, 99, 0, 99, 8, 7, 6, 5,
5, 6, 7, 8, 99, 0, 99, 8, 7, 6,
4, 5, 6, 7, 8, 99, 0, 99, 8, 7,
3, 4, 5, 6, 7, 8, 99, 0, 99, 8,
2, 3, 4, 5, 6, 7, 8, 99, 0, 99,
1, 2, 3, 4, 5, 6, 7, 8, 99, 0
};*/
int len =0;
int cost[5][5] =
{
99,7,99,6,88,
5,99,99,4,99,
99,99,99,99,8,
9,5,99,99,7,
99,99,4,6,99
};
int best[5][5];
int next[5][5];
int nodeCount = 5;
void Floyd()
{
int i,j,k;
for(i=0;i<nodeCount;i++)
for(j=0;j<nodeCount;j++)
{
best[i][j]=cost[i][j];
next[i][j]= (i == j ? -1:i);
}
for(k =0;k<nodeCount;k++)
for(i=0;i<nodeCount;i++)
if(i != k)
{
for(j=0;j<nodeCount;j++)
{
if(j != i && j!= k && best[i][j] > best[i][k]+best[k][j])
{
best[i][j] = best[i][k]+best[k][j];
next[i][j] = next[k][j]; //按照这种方法算出来的是前驱,也就是从i到j的路径中j前边的一个顶点。
//next[i][j] = next[i][k];
//next[i][j] = k;
}
}
}
}
int nextJump(int i,int j)//返回的是节点自身
{
if(i == j)
return i;
else if( next[i][j] == -1)
return -1;
else
return nextJump(i,next[i][j]);
}
/*
利用递归的方法把从i到j的路径打印出来
*/
void printPath(int i,int j)
{
if(i == j)
cout<<i<<" ";
else if(i == -1)
cout<<"no path";
else
{
printPath(i,next[i][j]);
cout<<j<<" ";
}
}
/*
这个里边path里半存放的是从i到j得所有中间节点
*/
void savePath(int i,int j)
{
if(i == j)
path.push_back(i);
else if(i == -1)
cout<<"no path";
else
{
savePath(i,next[i][j]);
path.push_back(j);
}
}
main()
{
Floyd();
for(int i=0;i<nodeCount;i++)
{
for(int j=0;j<nodeCount;j++)
{
//cout<<nextJump(i,j)<<" ";
//cout<<next[i][j]<<" ";
path.clear();
cout<<"path "<<i<<" => "<<j<<":";
savePath(i,j);
if(path.size() > 1)
cout<<path.at(1);
else
cout <<path.at(0);
cout<<endl;
}
cout<<endl;
}
return 0;
}
分享到:
相关推荐
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
Dijkstra、Floyd算法Matlab,Lingo代码的实现。
主要使用了Dijkstra算法,Floyd算法。 主要功能有六项:1、烟台大学的平面图。2、景点的介绍。3、从一个景点到其他地方的所有最短路径。4、两景点间的最短路径。5、计算从一个地方到另一个地方所要花费的时间。6、...
Floyd算法 详细介绍了Floyd算法的应用
给出一个带权有向图G=(V,E),其中每一条边(v,w)的权c[v,w]是一个非负实数。要求对任意的顶点有序对(v,w)找出从顶点v到顶点w的最短路径长度。这个问题就称为带权有向图的所有...另外,也可以采用的较直接的Floyd算法。
教科书上的Floyd算法只能输出path,无法给出具体的路径描述,本代码可以输出具体的路径选择
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
Floyd-Warshall算法,又叫Floyd算法,用于求每对顶点之间最短路径
使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。 核心思路 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
利用Floyd算法以及Dijkstra算法解决选址问题以及matlab代码文档
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
Floyd算法的应用研究,周柳阳,,我国地域辽阔,气候多变,各种自然灾害频频发生,特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害。提前做好某种
floyd算法,C语言编写的程序,适合学生作业。非常专业
C++实现floyd算法 希望大家指正出现的问题,多多下载,本人需要积分,谢谢大家
资源名:Floyd算法_floyd最短路算法_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定...
floyd算法,用java语言描述,图的最短路径算法,详细讲解