使用弗洛伊德(Floyd)算法求下面这每一对顶点之间的最短路径,实话出矩阵A0,A1,A2,A3中的情况(即A(0),A(1),A(2),A(3))。
#define MAX_V 4 int d[MAX_V][MAX_V];// d[u][v]表示e=(u,v)的路径总权值,也就是点u到点v的最短路径。初始化设为无穷大 //floyd 算法是动态规划算法,最短路径更新规则是 d[u][v] = min(d[u][v],d[u][k]+d[k][v]),0<k<MAX_V // 复杂度是O(n^3) void floyd(){ for(int k=0;k<MAX_V;k++){ for(int i=0;i<MAX_V;i++){ for(int j = 0;j<MAX_V;j++){ d[i][j] = min(d[i][j],d[i][k]+d[k][j]); } } } }