Question

求matlab高手，帮我解决一下floyd算法！！急急急

Answer 1

//假期在家做的，网上这类算法很多，思想都差不多
#include<iostream>
using namespace std;
int N; //顶点个数
int max = 10000; //max代表两点之间没有路径存在
float ** inPut(){
int edge,m,n,w,i;
cout<<"请输入顶点数：";
cin>>N;
N = N+1; //矩阵（数组）下标从1开始计数，方便操作
float **C = new float*[N]; //矩阵C为图的初始邻接矩阵
for(i = 1; i<N; i++)
*(C+i) = new float[N];

for( i = 1; i<N; i++) //邻接矩阵初始化
for(int j = 1; j<N; j++){
if(i == j)
C[i][j] = 0; //矩阵对角线上的值初始为0，其他为max
else C[i][j] = max;
}

cout<<"请输入边数：";
cin>>edge;
cout<<"请输入边及权值："<<endl;
for(i = 0; i<edge; i++){
cin >> m >> n >> w;
C[m][n] = w;
}
return C;
}
void Floyd(float **C){
int i,j;
float **A = new float*[N]; //矩阵A最终存放修改后的路径长度
int **path = new int*[N]; //矩阵path记录两点之间的路径
for(i = 1; i<N; i++)
*(A+i) = new float[N];
for(i = 1; i<N; i++)
*(path+i) = new int[N];
for(i = 1; i<N; i++) //设置矩阵A和path的初值
for(j = 1; j<N; j++){
if(C[i][j] != max)
path[i][j] = j; //存在路径，记录下终点下标值
else path[i][j] = -1; //不存在路径用-1表示

A[i][j] = C[i][j];
}
//修改路径长度（矩阵A）和路径（矩阵path）
for(int k = 1; k<N; k++) //试图将顶点k扩充到最短路径path矩阵中
for(i = 1; i <N; i++)
for(j = 1; j<N; j++)
if( A[i][j] > ( A[i][k]+A[k][j] ) ){//判断顶点i到j的权值是否大于从i经k到j的权值，取二者较小者记录下来
A[i][j] = ( A[i][k]+A[k][j]);
path[i][j] = path[i][k]; //记录下中间顶点k值
}

cout << endl << endl;
cout << "初始邻接矩阵C[N][N]" << endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << C[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;
cout << "修改后的路径长度矩阵" << endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << A[i][j] << "\t";
}
cout << endl;
}
cout << endl;
cout << endl;
cout<<"路径矩阵"<<endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << path[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;
cout << "所有顶点对之间的最短路径的权值及其路径" << endl;
for(i = 1; i<N; i++){
cout << endl;
for(j = 1; j<N; j++){
cout << A[i][j] << "\t"; //输出i-->j的权值
int next = path[i][j]; //顶点i到j的路径，i后的第一个后继顶点
if(next == -1) //路径不存在
cout << i << " 到 " << j << " 没有路径" << endl;
else {
cout<<i; //起点
while(next != j){ //i、j之间存在中间顶点
cout << "-->" << next;
next = path[next][j]; //寻找下一个中间顶点
}
cout << "-->" << j << endl; //终点
}
}
}
}
int main(int argc, char* argv[]){
float **C;
C = inPut(); //邻接矩阵的初始化
Floyd(C);
return 0;
}
/*
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
*/

Answer 2

很久以前写的一个程序，你可以参考下，floyd求各点之间的最短路径，w为点间距离矩阵，将下面函数放在 floyd.m文件中，然后直接调用即可！

function [D,R]=floyd(w)
%floyd程序
n=size(w,1);
% D[i,j] 为记录i,j两点间的路径长度,结果显示即为所求的各点见的最短路径
% R[i,j] 为记录插入点的信息，即vi到vj 需要经过的点，初始化R[i,j]=j
D=w;
%赋初值
for i=1:n
for j=1:n
R(i,j)=j;
end
end
%循环搜索
for k=1:n
for i=1:n
for j=1:n
if D(i,j)>D(i,k)+D(k,j)
D(i,j)=D(i,k)+D(k,j);
R(i,j)=R(i,k);
end
end
end
end