floyd算法c语言_最短路径算法 C语言

‘壹’ floyd算法最短路径 C语言

void Floyd(int **arr,int Vertex)
{
int i,j,k;
for(k=0;k<Vertex;k++)
for(i=0;i<Vertex;i++)
for(j=0;j<Vertex;j++)
{
if (arr[i][j]>arr[i][k]+arr[k][j])
{
arr[i][j] = arr[i][k]+arr[k][j];
}
}
}

‘贰’ 求计算机求解关系R的传递闭包 C语言算法

传递闭包,最简单的技术是采用【弗洛伊德算法】

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

Floyd-Warshall算法的原理是动态规划。

设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

1.若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
2.若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

代码请见：

‘叁’ 求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;

}
}

‘肆’ 一个c语言编程球最短路问题....

用floyd算法（时间复杂度为0(N*3)）
具体实现如下：
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin;
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;
}

‘伍’ C语言权值问题

floyd算法可以解决。
先设各个点不能访问自己，必须从别的点走回自己，算出各个点的环路，然后求出最小的即可。
文件的自己搞搞吧，
#include <stdlib.h>
#include <stdio.h>

#define INFINITE 0xFFFFFFFF

void
floyd(unsigned int* A, unsigned int* B, int n)
{
int i, j, k;
int minind;

for (i=0; i<n; i++)
for (j=0; j<n; j++)
A[i*n+j] = B[i*n+j];
for (i=0; i<n; i++)
A[i*n+i] = INFINITE;

for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
if ((A[i*n+k] != INFINITE) && (A[k*n+j] != INFINITE) && (A[i*n+k] + A[k*n+j] < A [i*n+j]))
A[i*n+j] = A[i*n+k] + A[k*n+j];

for (minind = 0,i=1; i<n; i++)
if(A[minind*n+minind] > A[i*n+i])
minind = i;
printf ("mincircle = %d\n", A[minind*n+minind]);
printf ("%d->", minind);
for (i=minind+1; (i%n)!=minind; i++)
if (A[minind*n+i]+A[i*n+minind] == A[minind*n+minind])
printf ("%d->", i);
printf ("%d", minind);
printf ("\n");
}

int main(int argc, char** argv)
{
int num, i, j;
unsigned int* A = NULL;
unsigned int* B = NULL;
while (scanf("%d", &num) == 1)
{
A = (unsigned int*) malloc (num * num * sizeof(unsigned int));
B = (unsigned int*) malloc (num * num * sizeof(unsigned int));
for (i=0; i<num; i++)
{
for (j=0; j<num; j++)
{
scanf ("%u", &B[i*num+j]);
}
}

floyd (A, B, num);
for (i=0; i<num; i++)
{
for (j=0; j<num; j++)
{
printf ("%u ", A[i*num+j]);
}
printf ("\n");
}
}
return 0;
}

‘陆’ 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)//符合你要求吗？

‘柒’ 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);
}

‘捌’ 数据结构C语言版Floyd算法

您的理解不太对啊，每个矩阵D中记录的都是顶点i到顶点j的当前所经顶点状态下的最短路径

‘玖’ 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
}

‘拾’ 最短路径算法 C语言

#include<stdio.h>

#defineMAXNODE108

intpath[MAXNODE+1][MAXNODE+1]={0};

intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;

fpr=fopen("in.txt","r");/*读取的文件名称in.txt*/
fpw=fopen("out.txt","w");/*path的数据在out.txt中展现*/

while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;

for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;

if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}

for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw,"
");
}

return0;
}

注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！

这是之前的答案的错误之处。

-1表示不通。

具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。

导航:首页 > 源码编译 > floyd算法c语言

floyd算法c语言

与floyd算法c语言相关的资料