本文目录
- floyd算法中输出最短路径序列的C语言代码
- matlab实现弗洛伊德算法的代码，
- 求一C# floyd算法代码
- Floyd算法的参考代码
- mfc中用弗洛伊德算法算最短距离的问题，求帮助看看这些代码什么意思
- floyd算法
- C++ 弗洛伊德算法
- 求解答以下Matlab Floyd算法代码的含义
- 弗洛伊德算法介绍 弗洛伊德算法资料
floyd算法中输出最短路径序列的C语言代码
void path(int i,int j)
{
int k;
if(P==FALSE)
printf(“There’s no path!“);
return;
for(k=0;k《n;k++)
if(P==TRUE)
{
path(i,k);
path(k,j);
break;
}
}
void print(){
int v,w,u,i;
for (v=0;v《n;++v)
{
for (w=0;w《n;++w)
printf(“ %d “,D);
printf(“\n“);
}
printf(“Please input the tailvex v1 and headvex v2:“);
scanf(“v1=%d,v2=%d“,&v,&w);
path(v,w);
}
以上两段应该对你有用。
matlab实现弗洛伊德算法的代码，
function
=floyd(a)
%floyd.m
%采用floyd算法计算图a中每对顶点最短路
%d是矩离矩阵
%r是路由矩阵
n=size(a,1);
d=a;
for
i=1:n
for
j=1:n
r(i,j)=j;
end
end
r
for
k=1:n
for
i=1:n
for
j=1:n
if
d(i,k)+d(k,j)
评论
0
0
0
加载更多
求一C# floyd算法代码
#include《stdio.h》
#include《string.h》
int path={0};
void p(int e,int s)
{
int k=path;
if(k!=0)
{
p(e,k);
printf(“ %d“,k);
p(k,s);
}
}
int main()
{
memset(path,0,sizeof(path));
int adj;
int n;
scanf(“%d“,&n);
for(int i=1;i《=n;i++)
for(int j=1;j《=n;j++)
{
scanf(“%d“,&adj);
if(adj=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)
{
adj;
path=k;
}
}
int s,e;
scanf(“%d%d“,&s,&e);
if(adj==65535)
printf(“No way!!\n“);
else
{
printf(“%d\n“,adj);
printf(“%d“,s);
p(s,e);
printf(“ %d\n“,e);
}
return 0;
}
/*
著名的floyd算法，它是多源最短路径算法，也就说可以给除任意两结点的最短路，
如果它们有路，时间复杂度O(n^3)算法分析：
先提出疑问，这个算法是怎样做到求最短路径的呢？
其实对于最短路，我们说的路最短也就是是权值最小，并不是单方面的说路的长度
这个权值可以是造价，耗费，长度，时间等等，我们首先要理解这一点。
从小张家到小李家有50米的路程，到小王家有10米，小王家到小李家20米远，这时我们
要从小张家到王家最少要走多远，答案是30米，我们选择路线的时候没有直接走过去，而且发现
了一中转点，可以使得整个路程更短。其实floyd就用了这种思想，第一个循环枚举了用哪个
点来作为中转，第二第三循环枚举从谁走到谁，通过枚举所有的情况，最后就会得到最小值。
这时你会想，一个最短路是看整体的整个图来确定的，为什么每次两个点就可以搞定呢？
其实是这样的，每个使用过的点，在前一阶段求出了一个值，这时候再用它就等于已经继承了
它前面所计算出来的最短路的值，同过这个最短值上再去选择一条路，然后新形成的路还是一条
最短路，只是起终点不一样罢了。
这个算法抽象度较高，需加以图解和多想，掌握这个算法比较重要，它的思想在以后的
图论学习中比较重要，特别是继承的这种思想和松弛技术。
*/
Floyd算法的参考代码
function Floyd(w,router_direction,MAX)
%w为此图的距离矩阵
%router_direction为路由类型：0为前向路由；非0为回溯路由
%MAX是数据输入时的∞的实际值
len=length(w);
flag=zeros(1,len);
%根据路由类型初始化路由表
R=zeros(len,len);
for i=1:len
if router_direction==0%前向路由
R(:,i)=ones(len,1)*i;
else %回溯路由
R(i,:)=ones(len,1)*i;
end
R(i,i)=0;
end
disp(’’);
disp(’w(0)’);
dispit(w,0);
disp(’R(0)’);
dispit(R,1);
%处理端点有权的问题
for i=1:len
tmp=w(i,i)/2;
if tmp~=0
w(i,:)=w(i,:)+tmp;
w(:,i)=w(:,i)+tmp;
flag(i)=1;
w(i,i)=0;
end
end
%Floyd算法具体实现过程
for i=1:len
for j=1:len
if j==i || w(j,i)==MAX
continue;
end
for k=1:len
if k==i || w(j,i)==MAX
continue;
end
if w(j,i)+w(i,k)《w(j,k) %Floyd算法核心代码
w(j,k)=w(j,i)+w(i,k);
if router_direction==0%前向路由
R(j,k)=R(j,i);
else %回溯路由
R(j,k)=R(i,k);
end
end
end
end
%显示每次的计算结果
disp()
dispit(w,0);
disp()
dispit(R,1);
end
%中心和中点的确定
=min(max(w’));
disp();
=min(sum(w’));
disp();
end
function dispit(x,flag)
%x：需要显示的矩阵
%flag：为0时表示显示w矩阵，非0时表示显示R矩阵
len=length(x);
s=;
for j=1:len
if flag==0
s=;
else
s=;
end
s=;
end
disp(s);
disp(’---------------------------------------------------’);
end
% 选择后按Ctrl+t取消注释号%
%
% 示例：
% a=[
% 0,100,100,1.2,9.2,100,0.5;
% 100,0,100,5,100,3.1,2;
% 100,100,0,100,100,4,1.5;
% 1.2,5,100,0,6.7,100,100;
% 9.2,100,100,6.7,0,15.6,100;
% 100,3.1,4,100,15.6,0,100;
% 0.5,2,1.5,100,100,100,0
% ];
%
% b=[
% 0,9.2,1.1,3.5,100,100;
% 1.3,0,4.7,100,7.2,100;
% 2.5,100,0,100,1.8,100;
% 100,100,5.3,0,2.4,7.5;
% 100,6.4,2.2,8.9,0,5.1;
% 7.7,100,2.7,100,2.1,0
% ];
%
% Floyd(a,1,100)
% Floyd(b,1,100) program floyd;
var
st,en,f:integer;
k,n,i,j,x:integer;
a:array of integer;
path:array of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(k);
if k《》0 then
a:=k
else
a:=maxint;
path:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a then
begin
a;
path;
end;
readln(st,en);
writeln(a);
f:=st;
while f《》 en do
begin
write(f);
write(’--》’);
f:=path;
end;
writeln(en);
end. //以无向图G为入口，得出任意两点之间的路径长度length);}}}
mfc中用弗洛伊德算法算最短距离的问题，求帮助看看这些代码什么意思
你这段代码里面sPath就定义的时候用了一次，后面都没用！！！ 我也没看懂这个作用！
是不是你的代码没贴全？
floyd算法
核心思路
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A= 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}
map表示i到j的最短距离
K是穷举i,j的断点
map初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理,比如没有map这条路
本段
算法过程
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G=空值。
定义一个矩阵D用来记录所插入点的信息，D=j。
把各个顶点插入图中，比较插点后的距离与原来的距离，G=k。
在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3，D(3,1)=2，D(2,1)=1则说明从V5到V1经过V3，从V3到V1经过V2，V2到V1直接相连，路径为{V5,V3,V2,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。
本段
时间复杂度
O(n^3)
本段
优缺点分析
Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；
缺点：时间复杂度比较高，不适合计算大量数据。
C++ 弗洛伊德算法
#include《cstdio》
#include《cstdlib》
using namespace std;
int map;
int main()
{
int m,n,i,j,k,x,y,a,b,t;
scanf(“%d“,&n,&m);
for(i=1;i《=n;i++)
for(j=1;j《=n;j++)
map=999999999;
for(i=1;i《=m;i++)
{
scanf(“%d%d%d“,&x,&y,&t);
map=t;
}
for(k=1;k《=n;k++)
{
for(i=1;i《=n;i++)
{
for(j=1;j《=n;j++)
{
if(map)
map;
}
}
}
scanf(“%d%d“,&a,&b);
printf(“%d\n“,map);
system(“pause“);
return 0;
}
第8行的scanf(“%d“,&n,&m);这里是不是写错了？
求解答以下Matlab Floyd算法代码的含义
暴力循环搜索。如果i，j之间存在k，使得i到j的距离大于i到k的距离加上k到j的距离，说明i--》k--j距离短，并把最短距离赋值给dij。很经典的最短路程序，只需要把距离矩阵套进去就行。
弗洛伊德算法介绍 弗洛伊德算法资料
1、Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
2、在计算机科学中，Floyd-Warshall算法是一种在具有正或负边缘权重（但没有负周期）的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度（加权）。虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径。该算法的版本也可用于查找关系R的传递闭包，或（与Schulze投票系统相关）在加权图中所有顶点对之间的最宽路径。
