前言

復習acwing演算法基礎課的內容，本篇為講解基礎演算法：Floyd，關于時間復雜度：目前博主不太會計算，先鴿了，日后一定補上，

一、什么是Floyd演算法

計算最短路演算法的一種，相較于Dijkstra，bellman-ford，spfa，Floyd演算法是計算多源最短路問題的演算法，下圖來自AcWing演算法基礎課：

在這里插入圖片描述

二、AcWing 854. Floyd求最短路

本題鏈接：AcWing 854. Floyd求最短路
本博客給出本題截圖：

在這里插入圖片描述

本題分析

dist陣列的含義是兩點之間的距離，例如dist[i][j]代表的是從i點到j點的距離

這里也同樣解釋一下為什么寫成if (dist[a][b] > INF / 2)
和bellman-ford演算法寫成這樣的原因一致，因為我們存在負權邊，所以就算是兩個正無窮的邊在更新的時候，正無窮和正無窮之間的邊權為負，那么另一個正無窮被更新的時候會是正無窮減去一個數，小于INF，故我們直接要求dist[a][b] > INF / 2即可.

演算法核心：

void floyd()
{
    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]);
}

AC代碼

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int dist[N][N];
int n, m, k;

void floyd()
{
    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]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ) 
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
            
    while (m -- )
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        
        dist[x][y] = min(dist[x][y], z);
    }
    
    floyd();
    
    while (k -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        
        if (dist[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", dist[a][b]);
    }
    
    return 0;
}

三、時間復雜度

關于Floyd演算法的時間復雜度以及證明，后續會給出詳細的說明以及證明程序，目前先鴿了，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282614.html

標籤：其他

上一篇：cobbler實作自動化安裝centos7,8

下一篇：影像旋轉平移、仿射變換、透視變換