首页 > 试题广场 >

使用弗洛伊德(Floyd)算法求下面这每一对顶点之间的最短路

[问答题]

使用弗洛伊德(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]);
       }
     }
   }
}

编辑于 2017-02-21 21:08:42 回复(0)