數(shù)據(jù)結(jié)構(gòu)與算法：Floyd算法

問(wèn)題描述實(shí)現(xiàn)Floyd算法，并求所示有向圖中各頂點(diǎn)之間的最短路徑及其長(zhǎng)度。算法思想采用圖的鄰接矩陣存儲(chǔ)，實(shí)現(xiàn)Floyd算法~，數(shù)組P[][][]存儲(chǔ)是否存在中間點(diǎn)使長(zhǎng)度縮短。設(shè)計(jì)描述數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)類型的定義：typedefstructMGraph{charvexs[MAX_VERTEX_NUM];intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum,arcnum;GraphKindkind;}MGraph;源程序#include<stdlib.h>#include<stdio.h>#defineINFINITY1000//最大值#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)#defineTRUE1#defineFALSE0typedefenum{DG,DN,UDG,UDN}GraphKind;//四種圖類型typedefstructMGraph{charvexs[MAX_VERTEX_NUM];//頂點(diǎn)向量intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKindkind;//圖的種類標(biāo)志}MGraph;voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,inta,intb);voidmain(){ MGraphG; intD[MAX_VERTEX_NUM][MAX_VERTEX_NUM],P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM]; intv,w,k,a,b,i; printf("請(qǐng)輸入頂點(diǎn)數(shù)和弧數(shù)"); scanf("%d%d",&G.vexnum,&G.arcnum); G.kind=DG; printf("請(qǐng)輸入鄰接矩陣\n");for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++) scanf("%d",&G.arcs[v][w]);//讀入鄰接矩陣 //P[v][w][k]為TRUE，則從v到w的最短路徑中含有k節(jié)點(diǎn) //D[v][w]從v到w的最短路徑的長(zhǎng)度 for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++){D[v][w]=G.arcs[v][w];for(k=0;k<G.vexnum;k++) P[v][w][k]=FALSE;if(D[v][w]<INFINITY)P[v][w][v]=P[v][w][w]=TRUE;}for(k=0;k<G.vexnum;k++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if(D[v][k]+D[k][w]<D[v][w]){D[v][w]=D[v][k]+D[k][w];for(i=0;i<G.vexnum;i++)P[v][w][i]=P[v][k][i]||P[k][w][i];} for(a=0;a<G.vexnum;a++) for(b=0;b<G.vexnum;b++) if(D[a][b]<INFINITY&&a!=b){ printf("%c到%c最短路徑為",65+a,65+b); printf("%c\t",65+a); find(P,G,a,b); printf("%c\t",65+b); printf("長(zhǎng)度為%d",D[a][b]); printf("\n"); }}voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,inta,intb){ intk; for(k=0;k<G.vexnum;k++) if(P[a][b][k]==TRUE&&k!=a&&k!=b){ find(P,G,a,k); printf("%c\t",65+k); find(P,G,k,b); }}測(cè)試結(jié)果輸入（1000為無(wú)窮！~輸出心得體會(huì)~。??！ 懂得了floyd算法的思想，用鄰接矩陣存儲(chǔ)帶權(quán)值的圖。 問(wèn)題主要出在輸出打印方面Voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,inta,intb){ intk; for(k=0;k<G.vexnum;k++) if(P[a][b][k]==TRUE&&k!=a&&k!=b){ find(P,G,a,k); printf("\t%c",65+