图算法一 —— 多源最短路径

• 多源最短路径
• • 题目
  • 思路
  • • C++代码

求取图中任意两个顶点之间的最短路径

Floyd算法

Floyd算法本质上是一个动态规划的思想，每一次循环更新经过前k个节点，i->j的最短路径

实际的思想就是：每次都考虑之前的路径，以及经过k节点，能否使得i->k + k->j < i->j

初始化dist数组时，使用int_max, i->j的路径填0

算法本质就是暴力搜索，但是这个题能搜出来就不错了，不能再强行考虑时间复杂度的问题

int dist[400][400];
void Floyd(int n)
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}