floyd演算法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寫給我。