$$\color{Red}{Floyd求最短路-三种语言实现全解析}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

1.时间复杂度方面
O（n^3）
2.算法原理
三重循环所以说是n三次方复杂度
唯一的细节：刷新最小值会把看似无穷的距离变小，所以和bellman_ford一样，看看是不是大于二分之一极限

for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int M = 210, idx, n, m, k;
    static final int MAX_VALUE = 0x3f3f3f3f;
    static int[] d = new int[M];
    static int[][] g = new int[M][M];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void floyd(){
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        k = Integer.parseInt(s1[2]);
//        Arrays.fill(h, -1);
        for (int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if (i != j)
                    g[i][j] = 0x3f3f3f3f;

        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            g[a][b] = Math.min(g[a][b], c);
        }
        floyd();
        while (k-- > 0) {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            if(g[a][b] > 0x3f3f3f3f / 2) System.out.println("impossible");
            else    System.out.println(g[a][b]);
        }
    }
}

python3 代码

N = 210
g = [[0x3f3f3f3f] * N for i in range(N)]

def floyd():
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

if __name__ == '__main__':
    n, m, k = map(int, input().split())
    for i in range(1,n+1):
        g[i][i] = 0 #自己到自己距离为0

    for i in range(m):
        a, b, w = map(int, input().split())
        g[a][b] = min(g[a][b], w)

    floyd()

    for i in range(k):
        x, y = map(int, input().split())
        if g[x][y] > 0x3f3f3f3f // 2:  print('impossible')
        else:   print(g[x][y])

C++ 代码

#include <iostream>

using namespace std;

const int N = 210, INF = 1e9;
int g[N][N];
int n, m, q;

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

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    //除自己到自己外，距离要初始化为无穷
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i == j)  g[i][j] = 0;
            else        g[i][j] = INF;

    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    floyd();

    while(q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);

        if(g[x][y] > INF / 2)   puts("impossible");
        else cout << g[x][y] << endl;
    }
    return 0;
}