算法设计与分析 课件 10.3.4-综合应用-最短路径问题-弗洛伊德算法.pptx

;思考：

如何求解任意两点间的最短路径？;?重复执行迪杰斯特拉(Dijkstra)算法|V|次。总的执行时间为O(|V|3)。;i;i;k=2时，d[2][i][j]得到中间点编号不超过2的最短路径长度，包括：;k=n时，d[n][i][j]得到中间点编号不超过n的最短路径长度，即i到j的最短路径长度。;;[例]给出一个有向网及其邻接矩阵A。用Floyd算法求该有向网中每对顶点之间的最短路径长度及其最短路径。;;;单选题。

以下说法正确的是（）。

A.Floyd算法适用于权值为负的情况

B.Floyd算法不适用于权值为负的情况;p(0)[i][j]=i的含义是：从vi到vj的最短路径中，vj的前驱结点为vi;单选题。

下图是最终得到的前驱矩阵，从V1到V3点的最短路径是（）。

A.v1-v4-v3

B.v1-v3

C.v1-v2-v4-v3

D.以上都不对

;void?floyd(){/*Floyd算法求解任意两点间的最短路径*/

/*初始化*/

????for(int?i=1;i=n;i++)

????????for(int?j=1;j=n;j++)

????????????d[0][i][j]=graph[i][j];

/*自底向上动态规划求解*/

????for(int?k=1;k=n;k++){

????????for(int?i=1;i=n;i++){

????????????for(int?j=1;j=n;j++){

????????????????d[k][i][j]=min(d[k-1][i][j],

d[k-1][i][k]+d[k-1][k][j]);

????????????}?

}

}

}