floyd算法代码
1. 求Floyd算法与选址C++原代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define MAX_NAME 20
#define MAX_INFO 200
typedef int VRType;
typedef char VertexType[MAX_NAME];
#define INFINITY 65535
#define MAX_VERTEX_NUM 50
typedef struct
...{
VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
struct MGraph
...{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum;
int arcnum;
};
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//返回顶点在图中的序号
int LocateVex(MGraph G,VertexType u)
...{
int i;
for(i =0; i< G.vexnum;i++)
...{
if(strcmp(u,G.vexs[i]) == 0)
return i;
}
return -1;
}
//read the file for creating the MGraph
int CreateDN(MGraph &G)
...{
FILE *fp;
char start_city_name[MAX_NAME];
char end_city_name[MAX_NAME];
int distance_of_city = 0;
fp=fopen("./ukcities.txt","r");
//init MGraph data
//顶点数量
G.vexnum = 0;
//初始化两点之间的弧长信息,在这里即为两个城市间的距离
//INFINITY在这里应当理解为无穷大的意思,65535只是一个参考值
for(int p=0;p<MAX_VERTEX_NUM;++p)
for(int k=0;k<MAX_VERTEX_NUM;++k)
G.arcs[p][k].adj = INFINITY;
for(p=0;p<MAX_VERTEX_NUM;++p)
strcpy(G.vexs[p],"");
int m = 0;
for(int i=0;i<MAX_VERTEX_NUM;i++)
...{
fscanf(fp,"%s",start_city_name);
if(LocateVex(G,start_city_name) == -1)
...{
strcpy(G.vexs[m++],start_city_name);
G.vexnum++;
//printf("City Name: %s ", start_city_name);
}
fscanf(fp,"%s",end_city_name);
if(LocateVex(G,end_city_name) == -1)
...{
strcpy(G.vexs[m++],end_city_name);
G.vexnum++;
//printf("City Name: %s ", end_city_name);
}
fscanf(fp,"%d",&distance_of_city);
int iStart = LocateVex(G,start_city_name);
int iEnd = LocateVex(G,end_city_name);
//两个城市间的距离
G.arcs[iStart][iEnd].adj = distance_of_city;
}
fclose(fp);
return 1;
}
//最短路径的floyd算法实现
void ShortestPathByFloyd(MGraph G,DistancMatrix &D)
...{
int u,v,w;
for(v=0;v<G.vexnum;v++)
...{
for(w=0;w<G.vexnum;w++)
...{
D[v][w] = G.arcs[v][w].adj;
}
}
for(u=0;u<G.vexnum;u++)
...{
for(v=0;v<G.vexnum;v++)
...{
for(w=0;w<G.vexnum;w++)
...{
if(D[v][u] + D[u][w] < D[v][w])
...{
D[v][w] = D[v][u] + D[u][w];
}
}
}
}
}
int GetTheShortestDistance(char start_city[],char end_city[])
...{
MGraph g;
CreateDN(g);
int i;
for(i=0;i<g.vexnum;i++)
...{
g.arcs[i][i].adj = 0;
}
DistancMatrix d;
ShortestPathByFloyd(g,d);
int nStart = LocateVex(g,start_city);
int nEnd = LocateVex(g,end_city);
if(nStart == -1)
...{
printf("This city is not exist:%s ",start_city);
return 0;
}
if(nEnd == -1)
...{
printf("This city is not exist:%s ",end_city);
return 0;
}
/**//*
int j;
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(d[i][j] == INFINITY)
{
printf("* ");
}
else
{
printf("%02d ",g.arcs[i][j]);
}
}
printf(" ");
}
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(d[i][j] == INFINITY)
{
printf("* ");
}
else
{
printf("%03d ",d[i][j]);
}
}
printf("@ ");
}
*/
if(d[nStart][nEnd] == INFINITY)
...{
return -1;
}
else
...{
return d[nStart][nEnd];
}
}
void main()
...{
int key;
char start_city[MAX_NAME];
char end_city[MAX_NAME];
do
...{
printf("Enter the start city name: ");
scanf("%s",start_city);
printf("Enter the end city name: ");
scanf("%s",end_city);
int nDistance = GetTheShortestDistance(start_city,end_city);
if(nDistance == -1)
...{
printf("Can't find the path from %s to %s ",start_city,end_city);
}
else
...{
printf("The shortest distance between %s and %s is %dkm ",start_city,end_city,nDistance);
}
printf("Press 'y' or 'Y' to continue or any key to quit! ");
}
while((key = getch()) == 'y' || key == 'Y');
}
源码下载:
http://dl2.csdn.net/down4/20070705/05162441547.rar
2. matlab实现弗洛伊德算法的代码，。
function
[d,r]=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
加载更多
3. 用你熟悉的语言实现Floyd算法，对于具有下面权重矩阵的有向图求解完全最短路径，截图给出运行结果
Floyd的关键是三重循环和松弛式d[i][j] = min(d[i][j], d[i][k] + d[k][j])，代码和注释如下所示：
#include<bits/stdc++.h>
usingnamespacestd;
constintINF=1000000000;
constintn=5;
//邻接矩阵
intd[][n]={
{0,2,INF,1,8},
{6,0,3,2,INF},
{INF,INF,0,4,INF},
{INF,INF,2,0,3},
{3,INF,INF,INF,0}
};
intmain()
{
//floyd
for(intk=0;k<n;++k)
for(inti=0;i<n;++i)
for(intj=0;j<n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//输出结果
for(inti=0;i<n;++i){
for(intj=0;j<n;++j){
if(j>0)printf("");
if(d[i][j]==INF)printf("INF");
elseprintf("%3d",d[i][j]);
}
puts("");
}
return0;
}
运行结果图：
4. floyd算法导游问题
因为你只记录了u是否是k到j的最短路径上的点。。。并没有记录他们的相对顺序啊
试一下这个代码可以不
voidPrintShortestPath(constMGraph*G,int(&p)[10][10][10],intst,inted){
inti;
for(i=0;i<G->vexnum;i++){
if(i!=st&&i!=ed&&p[st][ed][i]){
PrintShortestPath(G,p,st,i);
PrintShortestPath(G,p,i,ed);
return;
}
}
printf("-->%s",G->vexs[ed].name);
}
voidFloyd(MGraph*G)
//用Floyd算法求图中各对顶点v和w之间的最短路径P[v][w]及其
//带权长度D[v][w]。若P[v][w][u]为1，则u是从v到w当前求得最短
//路径上的顶点。
{
intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for(v=0;v<G->vexnum;v++)//各对结点之间初始已知路径及距离
for(w=0;w<G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vexnum;u++)
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w])//从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w];//修改权值
for(i=0;i<G->vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
while(flag)
{
printf("请输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
if(k<0||k>G->vexnum||j<0||j>G->vexnum)
{
printf("景点编号不存在!请重新输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
}
if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)
flag=0;
}
printf("%s",G->vexs[k].name);
PrintShortestPath(G,p,k,j);
printf("总路线长%dm ",D[k][j]);
}//Floydend
5. 求解答以下Matlab Floyd算法代码的含义
暴力循环搜索。如果i，j之间存在k，使得i到j的距离大于i到k的距离加上k到j的距离，说明i-->k--j距离短，并把最短距离赋值给dij。很经典的最短路程序，只需要把距离矩阵套进去就行。
6. matlab floyd 算法注释
A矩阵是邻接矩阵，对角线上为o，其余位置数字表示的是两点之间距离，比如A(1,2)=2,表示从第一个点到第二个点的距离为2.inf是无穷大的意思，这里表示没有直接沟通这两点的路。
n=length(D);设定n为D矩阵的长度。
接下来的两重循环，得到的R矩阵是n*n的矩阵，它每个数据表示的是路径，比如:R(1,3)=1;表示路径为:1-1-3.这里是初始化路径了。
后面的三重循环是floyd算法的关键所在，就是更新路线了。里面的那个判断指的是:
假设有3个点，1
2
3;如果我从1-2-3之间总距离小于1-3的距离，那么我R(1,3)=2;这就是选取更近的路线了。
最后的两个判断是为了不让曾经走过的点再次被遍历。就是不回头的意思了，这个一般都可以忽略了，你照打上去就是了。
不知道这样的解释你是否满意。
7. 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]这条路
编辑本段
算法过程
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。
定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。
把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=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算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；
缺点：时间复杂度比较高，不适合计算大量数据。
8. floyd算法中输出最短路径序列的C语言代码
void path(int i,int j)
{
int k;
if(P[i][j][i]==FALSE)
printf("There's no path!");
return;
for(k=0;k<n;k++)
if(P[i][j][k]==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[v][w]);
printf("\n");
}
printf("Please input the tailvex v1 and headvex v2:");
scanf("v1=%d,v2=%d",&v,&w);
path(v,w);
}
以上两段应该对你有用。
9. floyd算法杭电2544求指教，就一个点
for(int j=1;j<=n;j++)
{
f[i][j] = INF;
if(i==j)f[i][j] = 0;
}由这段代码知道i!=j时，i到j的距离初始为无穷大INF的啊。如果C>INF在进行加的时候可能出现溢出吧。也就是说可能会有干扰数据。
10. floyd算法的c程序代码
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p,q,k,m;
int Vertex,Line[Maxm];
int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p,Path[p][q]);
Root(Path[p][q],q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
for(p=1;p<=Vertex;p++)
if (Dist[p][k]>0)
for(q=1;q<=Vertex;q++)
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}