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
