賦權(quán)有向圖中心問題教程文件

賦權(quán)有向圖中心問題計算機<1>班余志萍問題描述:設(shè)G=(V,E)是一個賦權(quán)有向圖，v是G的一個頂點，v的偏心距定義為：Max{w∈V,從w到v的最短路徑長度}G中偏心距最小的頂點稱為G的中心。試利用Floyd算法設(shè)計一個求賦權(quán)有向圖中心的算法。實驗任務(wù)對于給定的賦權(quán)有向圖G,計算圖的中心。由文件input.txt給出輸入數(shù)據(jù)。第1行有2個正整數(shù)n和m,表示給定的圖G有n個頂點和m條邊，頂點編號為1,2,…,n。接下來的m行中，每行有3個正整數(shù)n,v,w,表示圖G的一條邊(u,v)及其邊權(quán)w。將計算出的圖的中心及其偏心距輸出到文件output.txt。第1行是中心的偏心距，第2行是中心的紡號。輸入文件示例Input.txt57124132158244255341453輸出文件示例Output.txt232.開辟一個動態(tài)數(shù)組c[n+1][n+1]，利用Floyd算法算出所有頂點對之間的最短路徑則：

c[n+1][n+1]：c[1]c[1]c[1]c[1]c[1]１０４２３６２∞０∞４５３∞∞０１４４∞∞∞０３５∞∞∞∞０3.在比較c[n+1][n+1]中的每一列中的最大值即為該列所對應(yīng)的頂點的偏心距，開辟一個動態(tài)數(shù)組max[n+1]，存放每個頂點的偏心距

max[n+1]： 0 4 2 4 64.從max[n+1]中找出偏心距最小的頂點并輸出其偏心距及編號核心代碼：for(i=1;i<=n;i++)//求出所有頂點對的最短距離 for(j=1;j<=n;j++){ c[i][j]=a[i][j]; } for(i=1;i<=n;i++) c[i][i]=0; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){ t1=c[i][k]; t2=c[k][j]; t3=c[i][j]; if(t1!=32768&&t2!=32768&&(t3==32768||t1+t2<t3)) c[i][j]=t1+t2; }for(j=1;j<=n;j++)//求所有頂點的偏心距 for(i=1;i<=n;i++) if((c[i][j]>max[j])&&(c[i][j]!=32768)) max[j]=c[i][j]; dis=32768;center=0;//找出最小的偏心距 for(i=1;i<=n;i++) if(max[i]<dis&&max[i]!=0) { dis=max[i]; center=i; } printf