c语言floyd算法
仅供参考~
#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_INT 10000 //无穷大
typedef int AdjType;
typedef struct{
int pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径
int end;
}PathType;
typedef char VType; //设顶点为字符类型
typedef struct{
VType V[MAX_VERTEX_NUM]; //顶点存储空间
AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
}MGraph;//邻接矩阵表示的图
//Floyd算法
//求网G（用邻接矩阵表示）中任意两点间最短路径
//D[][]是最短路径长度矩阵，path[][]最短路径标志矩阵
void Floyd(MGraph * G,int path[][MAX_VERTEX_NUM],int D[][MAX_VERTEX_NUM],int n){
int i,j,k;
for(i=0;i<n;i++){//初始化
for(j=0;j<n;j++){
if(G->A[i][j]<MAX_INT){
path[i][j]=j;
}else{
path[i][j]=-1;
}
D[i][j]=G->A[i][j];
}
}
for(k=0;k<n;k++){//进行n次试探
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(D[i][j]>D[i][k]+D[k][j]){
D[i][j]=D[i][k]+D[k][j];//取小者
path[i][j]=path[i][k];//改Vi的后继
}
}
}
}
}
int main(){
int i,j,k,v=0,n=6;//v为起点，n为顶点个数
MGraph G;
int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点的最短路径向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点最短路径长度向量
//初始化
AdjType a[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={
{0,12,18,MAX_INT,17,MAX_INT},
{12,0,10,3,MAX_INT,5},
{18,10,0,MAX_INT,21,11},
{MAX_INT,3,MAX_INT,0,MAX_INT,8},
{17,MAX_INT,21,MAX_INT,0,16},
{MAX_INT,5,11,8,16,0}
};
for(i=0;i<n;i++){
for(j=0;j<n;j++){
G.A[i][j]=a[i][j];
}
}
Floyd(&G,path,D,6);
for(i=0;i<n;i++){//输出每对顶点间最短路径长度及最短路径
for(j=0;j<n;j++){
printf("V%d到V%d的最短长度:",i,j);
printf("%d\t",D[i][j]);//输出Vi到Vj的最短路径长度
k=path[i][j];//取路径上Vi的后续Vk
if(k==-1){
printf("There is no path between V%d and V%d\n",i,j);//路径不存在
}else{
printf("最短路径为:");
printf("(V%d",i);//输出Vi的序号i
while(k!=j){//k不等于路径终点j时
printf(",V%d",k);//输出k
k=path[k][j];//求路径上下一顶点序号
}
printf(",V%d)\n",j);//输出路径终点序号
}
printf("\n");
}
}
system("pause");
return 0;
}
B. 离散数学Warshall算法求传递闭包C语言实现
#include <stdio.h>#include <stdlib.h>#define N 20#define M 20main(){ int i,j,k,m,n; int r1[M],r2[M],a[N],mr[N][N]={0}; FILE * fp; printf（＂程序自动调用c:/stone2.txt文件内相应数据\n＂）; fp=fopen(＂c:\\stone2.txt＂,＂r＂); fscanf(fp,＂%d＂,&n)； /*读取集合元素个数*/ for(i=0;i<n;i++) /*读取集合元素*/ fscanf(fp,＂%d＂,&a[i]); fscanf(fp,＂%d＂,&m)； /*读取关系个数*/ for(k=0;k<m;k++) fscanf(fp,＂%d,%d＂,&r1[k],&r2[k])； /*读取关系*/ fclose(fp); printf（＂自反闭包r(R):\n{＂); for(i=0;i<n;i++) printf(＂<%d,%d>,＂,a[i],a[i])； /*输出自反闭包*/ for(k=0;k<m;k++) { if(r1[k]!=r2[k]) printf(＂<%d,%d>,＂,r1[k],r2[k]); else continue; } printf(＂\b}\n＂); printf（＂对称闭包s(R):\n{＂）； /*输出对称闭包*/ for(k=0;k<m;k++) { if(r1[k]!=r2[k]) printf(＂<%d,%d>,<%d,%d>,＂,r1[k],r2[k],r2[k],r1[k]); else printf(＂<%d,%d>,＂,r1[k],r2[k]); } printf(＂\b}\n＂); k=0; for(i=0;i<n,k<m;i++) { if(r1[k]!=a[i]) continue; else { for(j=0;j<n,k<m;j++) /*关系转换成矩阵*/ { if(r2[k]!=a[j]) continue; else { mr[i][j]=1; k++; i=0;j=0; break; } } } } printf（＂关系所对应的关系矩阵：\n＂）; for(i=0;i<n;i++) { /*打印关系矩阵*/ for(j=0;j<n;j++) printf(＂%5d＂,mr[i][j]); printf(＂\n＂); } for(k=0;k<n;k++) for(i=0;i<n;i++) /*warshall*/ for(j=0;j<n;j++) mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j]; for(i=0;i<n;i++) for(j=0;j<n;j++) { /*把mr[]非0项赋值为1*/ if(!mr[i][j]) continue; else mr[i][j]=1; } printf（＂传递闭包对应关系矩阵：\n＂）; for(i=0;i<n;i++) { /*输出传递闭包对应的关系矩阵*/ for(j=0;j<n;j++) printf(＂%5d＂,mr[i][j]); printf(＂\n＂); } system(＂PAUSE＂)；}自己写的，三个闭包都有，包括传递闭包，看注释就知道了，还是用文件读写，方便数据输入
C. C语言编程floyd法求助
for(i=0;i<n;i++){//输出每对顶点间最短路径长度及最短路径
for(j=0;j<n;j++){
printf("%d到%d的最短长度:",i+1,j+1);
printf("%d\t",D[i][j]);//输出Vi到Vj的最短路径长度
printf("\n");
}
}
修改这里的就好了。不要全部输出。
你可以定义一个变量 来累加 D[I][J]初步想法
int minzise = 0;
for(i=0;i<n;i++){//输出每对顶点间最短路径长度及最短路径
for(j=0;j<n;j++){
minzise+= D[i][j];//
}
}
printf(“%d”),minzise)//符合你要求吗？
D. C语言最短路径算法问题，Floyd算法行不通
要用算法你也要先理解了再用啊，不懂你是修改了什么，反正floyd肯定不是你这么写，floyd要把中间结点的遍历放在最三重循环的最外层。另外，求最短路径是怎么走的完全可以在更新最短路径长度的过程中记录中间结点是什么，这并非算法不能解决，而在于使用算法的人是否真正懂得算法过程，以及待解决的问题是否需要求解这方面的问题。
E. 用C语言实现以下问题并讲解大概思路和所用算法，非常感谢！
唔，你这个问题的话，因为你这个不指定起点，所以应该是多源最长路径问题，我参考了一下多源最短路径的Floyd算法如下，不知道可不可以啊：
首先是输入
g[i][j]表示从i城市到j城市所需要的路费，
int g[M][M]={{null,2,1,null},{null,null,5,4},{null,null,null,null},{null,null,null,null}}
null表示两个城市之间不存在路径，看上去这个数组很浪费，因为Floyd算法是可以针对更复杂的图进行计算的算法，具体有没有更优算法我也不知道=。=
然后让M=你输入的城市数量-1，这里M=4
输入设置好以后，就可以进行循环比较了，通过三重循环的比较，最终得到D[4][4]这样一个数组，这个数组中的D[i][j]表示从i城市到j城市所需要的最高的路费，然后再通过比较数组D中最大值，应该就可以得出结果了。
这里复制一下原理：
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。（而我们是求最长，所以应该换成max就可以了）
void floyd(int g[M][M],int D[M][M])
{
for(int k = 0;k<M;k++)
for(int i = 0;i<M;i++)
{
for(int j = 0;j<M;j++)
{
if(k == 0)//k=0，第一轮循环时，先将基础值赋值给D数组
{
if(g[i][j]!=null)
D[i][j] =g[i][j];
else
{
g[i][j]=-30000;//在k=0的第一轮循环中，让没有路径的地方等于一个大的负数，这样之后的比较就不需要重复的判断非空了
D[i][j]=-30000;
}}
else//当k不等于0时，也就是第二轮循环之后,进行最长路径的比较和计算，大的值赋值给D数组
{
D[i][j] = MAX(D[i][j],D[i][k]+D[k][j]);
}
}
}
}
最后再写个循环，取出数组D中的最大值就可以得到最大路程了然后再算最大路费，如果前面的算法没错的话。
我的感觉的话，Floyd-Warshall算法比较容易实现，不需要特殊的数据结构，就是可能算法的时间和空间复杂度比较高，不知道你怎么看
F. c语言问题.
Dijkstra算法可描述如下:
1初始化： S ← { v0 };
dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
// n为图中顶点个数
2求出最短路径的长度：
dist[k] ← min{ dist[i] }, i V- S ;
S ← S U { k };
3修改：
dist[i] ← min{ dist[i], dist[k] + Edge[k][i] },
对于每一个 i V- S ;
4判断： 若S = V, 则算法结束，否则转2。
用于计算最短路径的图邻接矩阵类的定义
const int NumVertices = 6; //图中最大顶点个数
class Graph { //图的类定义
private:
int Edge[NumVertices][NumVertices]; //邻接矩阵
int dist[NumVertices]; //最短路径长度数组
int path[NumVertices]; //最短路径数组
int S[NumVertices]; //最短路径顶点集
public:
void ShortestPath ( const int, const int );
int choose ( const int );
};
计算从单个顶点到其它各个顶点的最短路径
void Graph::ShortestPath ( const int n, const int v ){
//Graph是一个具有n个顶点的带权有向图, 各边上
//的权值由Edge[i][j]给出。本算法建立起一个数
//组: dist[j], 0 j < n, 是当前求到的从顶点v到顶点
//j的最短路径长度, 同时用数组path[j], 0 j < n, 存
//放求到的最短路径。
for ( int i = 0; i < n; i++) {
dist[i] = Edge[v][i]; //dist数组初始化
S[i] = 0;
if ( i != v && dist[i] < MAXINT ) path[i] = v;
else path[i] = -1; //path数组初始化
}
S[v] = 1; dist[v] = 0; //顶点v加入顶点集合
//选择当前不在集合S中具有最短路径的顶点u
for ( i = 0; i < n-1; i++ ) {
int min = MAXINT; int u = v;
for ( int j = 0; j < n; j++ )
if ( !S[j] && dist[j] < min )
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点u加入集合S
for ( int w = 0; w < n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXINT &&
dist[u] + Edge[u][w] < dist[w] ) {
dist[w] = dist[u] + Edge[u][w];
path[w] = u;
}
Floyd算法的基本思想：
定义一个n阶方阵序列：
A(-1), A(0), …, A(n-1).
其中 A(-1) [i][j] = Edge[i][j]；
A(k) [i][j] = min { A(k-1)[i][j]，
A(k-1)[i][k] + A(k-1)[k][j] }, k = 0,1,…, n-1
A(0) [i][j]是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)[i][j]是从顶点vi 到vj 的最短路径长度。
所有各对顶点之间的最短路径
void Graph::AllLengths ( const int n ) {
//Edge[n][n]是一个具有n个顶点的图的邻接矩阵。//a[i][j]是顶点 i 和 j 之间的最短路径长度。path[i][j]
//是相应路径上顶点 j 的前一顶点的顶点号, 在求
//最短路径时图的类定义中要修改path为
//path[NumVertices][NumVertices]。
for ( int i = 0; i < n; i++ ) //矩阵a与path初始化
for ( int j = 0; j < n; j++ ) {
a[i][j] = Edge[i][j];
if ( i <> j && a[i][j] < MAXINT )
path[i][j] = i; // i 到 j 有路径
else path[i][j] = 0; // i 到 j 无路径
}
for ( int k = 0; k < n; k++ ) //产生a(k)及path(k)
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
if ( a[i][k] + a[k][j] < a[i][j] ) {
a[i][j] = a[i][k] + a[k][j];
path[i][j] = path[k][j];
} //缩短路径长度, 绕过 k 到 j
}
G. floyd算法中输出最短路径序列的C语言代码
floyd是动态规划的简化,所以输出路径一样套用dp的典型记录方式即可.
即,每次松弛时,记录是松弛了哪一个点.然后输出时递归输出即可.
弄一个矩阵R[][]初始化为0,然后比如你的距离矩阵是D[][]
松弛改为是:
if(D[i][j] > D[i][k]+D[k][j]){
D[i][j] = D[i][k]+D[k][j];
R[i][j] = k;
}
输出时可以写一个递归函数
function out(a,b){
if(R[a][b] == 0){
return;
}
out(a,R[a][b]);
//输出k
out(R[a][b],b);
}
H. 数据结构C语言版Floyd算法
您的理解不太对啊，每个矩阵D中记录的都是顶点i到顶点j的当前所经顶点状态下的最短路径
I. 求floyd最短路径算法，c语言代码；
就是一个三重循环，核心代码就这几行
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
J. Warshall算法的算法介绍
1、引言
Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：
（1）置新矩阵A=M;
（2）置k=1;
（3）对所有i如果A[i,k]=1，则对j=1..n执行：
A[i,j]←A[i,j]∨A[k,j];
（4）k增1;
（5）如果k≤n，则转到步骤（3），否则停止。
所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。
在左孝凌等编着的《离散数学》中提到了该算法，但并未对此算法作出解释。下面本文将对该算法的思想作出一种比较通俗的解说。
2、对Warshall算法的解说
设关系R的关系图为G，设图G的所有顶点为v1,v2,…,vn，则t(R)的关系图可用该方法得到：若G中任意两顶点vi和vj之间有一条路径且没有vi到vj的弧，则在图G中增加一条从vi到vj的弧，将这样改造后的图记为G’，则G’即为t(R)的关系图。G’的邻接矩阵A应满足：若图G中存在从vi到vj路径，即vi与vj连通，则A[i,j]=1，否则A[i,j]=0。
这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。
定义一个n阶方阵序列A(0),A(1),A(2),…,A(n)，每个方阵中的元素值只能取0或1。A(m)[i,j]=1表示存在从vi到vj且中间顶点序号不大于m的路径（m=1..n），A(m)[i,j]=0表示不存在这样的路径。而A(0)[i,j]=1表示存在从vi到vj的弧，A(0)[i,j]=0表示不存在从vi到vj的弧。
这样，A(n)[i,j]=1表示vi与vj连通，A(n)[i,j]=0表示vi与vj不连通。故A(n)即为t(R)的关系矩阵。
那么应如何计算方阵序列A(0),A(1),A(2),…,A(n)呢？
很显然，A(0)=M（M为R的关系矩阵）。
若A(0)[i,1]=1且A(0)[1,j]=1，或A(0)[i,j]=1，当且仅当存在从vi到vj且中间顶点序号不大于1的路径，此时应将A(1)[i,j]置为1，否则置为0。
一般地，若A(k-1)[i,k]=1且A(k-1)[k,j]=1，或A(k-1)[i,j]=1，当且仅当存在从vi到vj且中间顶点序号不大于k的路径，此时应将A(k)[i,j]置为1，否则置为0（k=1..n）。用公式表示即为：
A (k)[i,j]=(A(k-1)[i,k]∧A(k-1)[k,j])∨A(k-1)[i,j] i,j,k=1..n
这样，就可得计算A(k)的方法：先将A(k)赋为A(k-1)；再对所有i=1..n，若A(k)[i,k]=1（即A(k-1)[i,k]=1），则对所有j=1..n，执行：
A (k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]
但这与前述Warshall算法中的第（3）步还有一定距离。若将上式改为：
A(k)[i,j]←A(k)[i,j]∨A(k)[k,j] （即把A(k-1)[k,j]改为A(k)[k,j]）
就可将上标k去掉，式子就可进一步变为：
A[i,j]←A[i,j]∨A[k,j]
这样可以只用存储一个n阶方阵的空间完成计算，且与前述Warshall算法中第（3）步的式子一致。那么，可不可以把A(k-1)[k,j]改为A(k)[k,j]呢？答案是肯定的。下面将证明在计算A(k)的过程中A(k-1)[k,j]与A(k)[k,j]相等（A(k)被赋初值A(k-1)后）。考察计算A(k)的方法 只有当i=k时A(k)[k,j]的值才有可能改变，此时将式A(k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]中的i换为k，得A(k)[k,j]←A(k)[k,j]∨A(k-1)[k,j]，对某一j，执行该式的赋值操作前A(k)[k,j]=A(k-1)[k,j]，因为计算A(k)开始时A(k)被赋为A(k-1)，故它们相或的结果等于A(k-1)[k,j]，故赋值操作不改变A(k)[k,j]的值。这样，就没有操作会改变A(k)[k,j]的值，故A(k-1)[k,j]与A(k)[k,j]相等。
综上，就可得到计算A(n)的算法，且该算法与前述的Warshall算法完全一致。
由上面的分析，不难看出，Warshall算法类似于求图中每对顶点间最短路径的Floyd算法。其实，用Floyd算法也能求关系的传递闭包，方法为令关系R的关系图G中的每条弧的权值都为1，这样得一有向网G1，设G1的邻接矩阵为D(-1)（若vi无自回路，则D(-1)(i,i)=∞），对G1用Floyd算法求其每对顶点间最短路径，得结果矩阵D(n-1)。因若G中vi与vj连通，当且仅当D(n-1)[i,j]≠∞，故将矩阵D中的∞都改为0，其它值都改为1，得矩阵A，则矩阵A即为t(R)的关系矩阵。Floyd算法和Warshall算法的时间复杂度都为O(n3)，但明显用Floyd算法求关系的传递闭包绕了弯子。
参考文献：
[1]左孝凌，李为鉴，刘永才，《离散数学》，上海：上海科学技术文献出版社，1982
[2]严蔚敏，吴伟民，《数据结构 C语言版》，北京：清华大学出版社，1997
