數據結構之---C語言實現最短路徑之Floyd（弗洛伊德）算法

數據結構之---C語言實現最短路徑之Floyd（弗洛伊德）算法

//此代碼綜合網絡上的代碼。
//弗洛伊德算法Floyd代碼
//楊鑫
#include 
#include 
#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;

int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各頂點的最短路徑向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各頂點最短路徑長度向量 
    

//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;iA[i][j]A[i][j];
        }
    } 
    
	//進行n次搜索
    for(k=0;k 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;
    
    //初始化 
    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
 
 
結果：