锐客网

  1. 首页 > 睿知 > it技术 > >

弗洛伊德算法代码java 弗洛伊德算法代码实现( 二 )

IT技术出题


if(D[v][w]INFINITY)//从v到w有直接路径
P[v][w][v]=w;
}
}
for(int k=0;kG.vexnum;++k)
{
for(int v=0;vG.vexnum;v++)
for(int w=0;wG.vexnum;++w)
if(D[v][w]D[v][k]+D[k][w])
{
D[v][w]=D[v][k]+D[k][w];
for(int i=0;iG.vexnum;i++)
{
if(P[v][k][i]!=-1)//原来存了顶点
P[v][w][i]=P[v][k][i];
else
P[v][w][i]=P[k][w][i];
}
}
}
}
//输出弗洛伊德中的最短路径
void output_shortestPath_FLOYD(MGraph G)
{
for(int i=0;iG.vexnum;++i)
{
for(int j=0;jG.vexnum;++j)
{
if(i!=j)//自己不能到达自己
{
coutG.vexs[i]"-"G.vexs[j]":";
if(D[i][j]==INFINITY)
{
cout"此两顶点之间不存在路径"endl;
}
else
{
cout"最短路径长度为:"" "D[i][j]" ";
cout"最短路径为:";
coutG.vexs[i];
for(int k=i;k!=-1;k=P[i][j][k])
{
if(k!=i)
coutG.vexs[k];
}
coutendl;
}
}
}
}
}
int main()
{
int num1;//顶点个数
int num2;//弧个数
cout"请输入顶点个数:";
cinnum1;
cout"请输入弧个数:";
cinnum2;
VertexType v;
MGraph G;
InitialMGraph(G);
cout"请输入顶点的信息:"endl;
for(int i=0;inum1;++i)
{
cinv;;
InsertVex(G,v);
}
VertexType v1,v2;
for(int j=0;jnum2;++j)
{
cout"请输入两个结点数据来表示的边:";
cinv1v2;
InsertArc(G,v1,v2);
}
ShortestPath_DIJ(G,0);
cout"迪杰斯特拉中的最短路径如下:"endl;
output_ShortestPath_DIJ(G,0);
coutendlendl;
shortestPath_FLOYD(G);
cout"弗洛伊德中的最短路径如下:"endl;
output_shortestPath_FLOYD(G);
return 0;
}
弗洛伊德的算法（Floyd’s algorithm ）假设这个图的weight matrix存在map[5][5]中弗洛伊德算法代码java，
for (int k=0; k5; k++)
for (int i=0; i5; i++)
for (int j=0; j5; j++) if (i != j) {
if (map[i][k] + map[k][j]map[i][j])
map[i][j] = map[i][k] + map[k][j];
}
处理完之后map[i][j]存的就是i弗洛伊德算法代码java，j之间的最短路径长度 。
简单的说，当执行完一次最外层循环时，map记录的时i，j之间允许使用中间节点｛0, ..., k｝的最短路径 。
求数据结构公交线路咨询的代码用java，其中求最短路径用Floyd算法不知道你想怎么搞反正感觉A*算法也可以，网上一大堆，还有就是Dijkstra算法
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]这条路
弗洛伊德算法代码java的介绍就聊到这里吧 ， 感谢你花时间阅读本站内容，更多关于弗洛伊德算法代码实现、弗洛伊德算法代码java的信息别忘了在本站进行查找喔 。

推荐阅读


上一篇：工业无线网络怎么用路由器，迷你路由器怎么设置无线网络

下一篇：word怎么设置段后距，word中如何设置段后间距