本文主要是介绍【备战蓝桥杯系列】多源最短路弗洛伊德floyd算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
floyd算法
蓝桥杯中,有时也会要求图中任意点的最短路径,这时候虽然可以用dijkstra,但是代码长,用floyd是最短的。模板如下。
模版
时间复杂度O(n^3)
使用邻接矩阵存储图
初始化:for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = INF;// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{for (int k = 1; k <= n; k ++ )//无脑通过中间点暴力循环for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
这篇关于【备战蓝桥杯系列】多源最短路弗洛伊德floyd算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!