?? 最短路徑(多源floyd_warshall鄰接陣形式).txt
字號:
//多源最短路徑,floyd_warshall算法,復雜度O(n^3)
//求出所有點對之間的最短路經,傳入圖的大小和鄰接陣
//返回各點間最短距離min[]和路徑pre[],pre[i][j]記錄i到j最短路徑上j的父結點
//可更改路權類型,路權必須非負!
#define MAXN 200
#define inf 1000000000
typedef int elem_t;
void floyd_warshall(int n,elem_t mat[][MAXN],elem_t min[][MAXN],int pre[][MAXN]){
int i,j,k;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
min[i][j]=mat[i][j],pre[i][j]=(i==j)?-1:i;
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (min[i][k]+min[k][j]<min[i][j])
min[i][j]=min[i][k]+min[k][j],pre[i][j]=pre[k][j];
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -