金坛城乡建设管理网站,一级a做爰片免费的网站有吗,alexa排名搜索,个人手机网站开发数据结构–最短路径 Floyd算法 F l o y d 算法#xff1a;求出每⼀对顶点之间的最短路径 \color{red}Floyd算法#xff1a;求出每⼀对顶点之间的最短路径 Floyd算法#xff1a;求出每⼀对顶点之间的最短路径 使⽤动态规划思想#xff0c;将问题的求解分为多个阶段 对于n个顶…数据结构–最短路径 Floyd算法 F l o y d 算法求出每⼀对顶点之间的最短路径 \color{red}Floyd算法求出每⼀对顶点之间的最短路径 Floyd算法求出每⼀对顶点之间的最短路径 使⽤动态规划思想将问题的求解分为多个阶段 对于n个顶点的图G求任意⼀对顶点 V i → V j V_i \to V_j Vi→Vj 之间的最短路径可分为如下⼏个阶段 #初始不允许在其他顶点中转最短路径是 #0若允许在 V0 中转最短路径是 #1若允许在 V0、V1 中转最短路径是 #2若允许在 V0、V1、V2 中转最短路径是 … #n-1若允许在 V0、V1、V2 …… Vn-1 中转最短路径是
Floyd算法是一种用于寻找图中任意两个节点之间最短路径的算法它的步骤如下
创建一个二维数组dist用于存储任意两个节点之间的最短路径长度。初始时dist的值为图中两个节点之间的直接路径长度如果两个节点之间没有直接路径则设置为无穷大。创建一个二维数组path用于存储任意两个节点之间的最短路径的中间节点。初始时path的值为起始节点到终点节点的直接路径上的终点节点。使用三重循环遍历所有节点每次循环中选择一个节点k作为中间节点更新dist和path数组的值。 a. 对于每对节点i和j如果通过节点k可以使得从节点i到节点j的路径更短则更新dist[i][j]的值为dist[i][k] dist[k][j]并更新path[i][j]的值为节点k。 b. 如果dist[i][j]的值变小了说明找到了一条更短的路径需要更新path[i][j]的值为节点k。重复步骤3直到遍历完所有节点。根据path数组可以构建任意两个节点之间的最短路径。
以上就是Floyd算法的基本步骤。
Floyd算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3)其中n为节点的个数。 若 A ( k − 1 ) [ i ] [ j ] A ( k − 1 ) [ i ] [ k ] A ( k − 1 ) [ k ] [ j ] 则 A ( k ) [ i ] [ j ] A ( k − 1 ) [ i ] [ k ] A ( k − 1 ) [ k ] [ j ] ; path ( k ) [ i ] [ j ] k 否则 A ( k ) 和 path ( k ) 保持原值 \begin{aligned} \text{若} \mathrm{A}^{(k-1)}[i][j]\mathrm{}\mathrm{A}^{(k-1)}[i][k]\mathrm{}\mathrm{A}^{(k-1)}[k][j] \\ \text{则} \mathbf{A}(k)[i][j]\mathbf{A}^{(k-1)}[i][k]\mathbf{A}^{(k-1)}[k][j]; \\ \operatorname{path}^{(k)}[i][j]k \\ \text{否则} A^{(k)}\text{ 和 path}^{(k)}\text{ 保持原值} \end{aligned} 若则否则A(k−1)[i][j]A(k−1)[i][k]A(k−1)[k][j]A(k)[i][j]A(k−1)[i][k]A(k−1)[k][j];path(k)[i][j]kA(k) 和 path(k) 保持原值 V0到V4 最短路径⻓度为 A[0][4]4 通过path矩阵递归地找到完整路径 注 Floyd算法可以⽤于负权图 Floyd 算法不能解决带有“负权回路”的图有负权值的边组成回路这种图有可能没有最短路径
eg: ## 代码
void floyd()
{
for(int i 1; i n; i)
for(int j 1; j n; j){
dist[i][j] map[i][j],
path[i][j] 0; }
for(int k 1; k n; k)
for(int i 1; i n; i)
for(int j 1; j n; j)
if(dist[i][k] dist[k][j] dist[i][j]){
dist[i][j] dist[i][k] dist[k][j];
path[i][j] k; //中转点}}知识点回顾与重要考点 注也可⽤ Dijkstra 算法求所有顶点间的最短路径重复 |V| 次即可总的时间复杂度也是 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)
