Floyd算法——最短路徑

用floyd算法求每對頂點間的最短路

其中：

//建立有向圖的鄰接矩陣

#include<stdio.h>
//-------------------------圖的鄰接矩陣存儲表示---------------------------
#define MaxInt 32767		//表示極大值，即無窮
#define MVNum 20		//最大頂點數
typedef char VerTexType;		//假設頂點的資料類型為字元型
typedef int ArcType;		//假設邊的權值類型為整型
typedef struct
{
	VerTexType vexs[MVNum];		//頂點表
	ArcType arcs[MVNum][MVNum];		//鄰接矩陣
	int vexnum,arcnum;		//圖目前點數和邊數
}AMGraph;


void CreateUDN(AMGraph *G);
int LocateVex(AMGraph G, char v);
void ShortestPath_Floyd(AMGraph G);

int main()
{
	AMGraph G;
	CreateUDN(&G);
	ShortestPath_Floyd(G);
	return 0;
}

//------------------------------采用鄰接矩陣建立有向網-----------------------------
void CreateUDN(AMGraph *G)
{
	int i,j,k,w;
	char v1,v2;
	printf("請輸入總的頂點數和總邊數：");
	scanf("%d %d",&G->vexnum,&G->arcnum);
	getchar();
	printf("請依次輸入頂點資訊：");
	for(i=0;i < G->vexnum;i++)
		scanf("%c",&G->vexs[i]);
	getchar();
	for(i=0;i<G->vexnum;i++)		//初始化鄰接矩陣，權值均設為MaxInt
		for(j=0;j<G->vexnum;j++)
			G->arcs[i][j]=MaxInt;
	for(k=0;k<G->arcnum;k++)
	{
		printf("請輸入第%d條邊依附的兩個頂點：",k+1);
		scanf("%c%c",&v1,&v2);
		getchar();
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);		//确定v1,v2在G中的位置，即頂點數組的下标
		printf("請輸入第%d條邊的權值：",k+1);
		scanf("%d",&w);
		getchar();
		G->arcs[i][j]=w;
	}
	return ;
}

//-----------------------定位函數----------------------
int LocateVex(AMGraph G,char v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		if(G.vexs[i]==v)
			return i;
	}
}

//----------------------floyd算法求每對頂點間的最短路--------------------
void ShortestPath_Floyd(AMGraph G)
{
	int Path[G.vexnum][G.vexnum],D[G.vexnum][G.vexnum];
	int i,j,k;
	for(i=0;i<G.vexnum;i++)				//對各結點之間初始已知路徑及距離
		for(j=0;j<G.vexnum;j++)
		{
			D[i][j]=G.arcs[i][j];
			if(D[i][j]<MaxInt&&i!=j)
                Path[i][j]=i;           //如果i和j之間有弧，則将j的前驅置為i
            else Path[i][j]=-1;         //如果i和j之間沒有弧，則将j的前驅置為-1
		}
    for(k=0;k<G.vexnum;k++)
        for(i=0;i<G.vexnum;i++)
            for(j=0;j<G.vexnum;j++)
            if(D[i][k]+D[k][j]<D[i][j])     //從i經k到j的一條路更短
            {
                D[i][j]=D[i][k]+D[k][j];
                Path[i][j]=Path[k][j];      //更新j的前驅為k
            }
    printf("\n--------------------------輸出結果-----------------------\n");
    int a[G.vexnum-2];
    int c;
    for(i=0;i<G.vexnum;i++)
        for(j=0;j<G.vexnum;j++)
        {
            if(i==j) continue;
            printf("%c到%c之間的最短距離是：%4d   ",G.vexs[i],G.vexs[j],D[i][j]);
            k=Path[i][j];
            c=0;
            while(k!=i)
            {
                a[c]=k;
                k=Path[i][k];
                c++;
            }
            printf("最短路徑為：%c->",G.vexs[i]);
            if(c>0)
            {
                for(c=c-1;c>=0;c--)
                    printf("%c->",G.vexs[a[c]]);
            }
            printf("%c",G.vexs[j]);
            printf("\n");
        }
    return ;
}