【ACM程式設計】求短路 Floyd演算法

• 2022 年 4 月 30 日
• 筆記
• 演算法

最短路

floyd演算法

• floyd是一個基於貪心思維和動態規劃思維的計算所有點到所有點的最短距離的演算法。

P57-圖-8.Floyd演算法_嗶哩嗶哩_bilibili

對於每個頂點v，和任一頂點對(i,j)，i=j,v=i, v≠j,如果A[i][j]> A[i][v]+ A[v][j]，則將 A[i][j] 更新
為 A[i][v] + A[v][j]的值,並且將 Path[i][j]改為v。

void Floyd(int n,float MGraph[][n],int Path[][n])
{
    int i,j,v;
    int A[n][n];
    //初始化A數組和Path數組
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            A[i][j]=MGraph[i][j];
            Path[i][j]=-1;
        }
    //進行Floyd演算法
    for(v=0;v<n;v++)
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(A[i][j]>A[i][v]+A[v][j])
                {
                    A[i][j]=A[i][v]+A[v][j]
                        Path[i][j]=v;
                }
}

void printPath(int u,int v,int path[][max])
{
    if(path[u][v]==-1)
        printf("<%d,%d> ",u,v);
    else
    {
        int mid=path[u][v];
        printPath(u,mid,path);
        printPath(mid,v,path);
    }
}

floyd例題

U80592 【模板】floyd - 洛谷 | 電腦科學教育新生態 (luogu.com.cn)

題目背景

模板題，無背景

題目描述

給出n個點，m條邊的無向圖，求每個點到其他點的距離之和%998244354的值

輸入格式

第一行兩個數n，m含義如上 從第二行開始，共m行，每行三個數x，y，l，代表從x到y點的長度為l

輸出格式

n行，每行一個數，第i行代表點i到其他點的距離之和

輸入輸出樣例

輸入 #1複製

2 1
1 2 4

輸出 #1

4
4

輸入 #2

4 5
1 2 1
1 3 2
2 3 2
3 4 3
2 4 4

輸出 #2

8
7
7
12

說明/提示

模板題，保證圖聯通 n<=500 m<=10000 1<=x,y<=n l<=1e9

#include <stdio.h>
#define MaxN 501
#define MOD 998244354
long long distance[ MaxN ][ MaxN ];

void floyd( int pointnum ) {
	int i, j, k;
	for ( k = 1; k <= pointnum; k ++ ) {
		for ( i = 1; i <= pointnum; i ++ ) {
			for ( j = 1; j <= pointnum; j ++ ) {
				if ( distance[ i ][ k ] != -1 && distance[ k ][ j ] != -1 ) {
					if ( distance[ i ][ j ] > distance[ i ][ k ] + distance[ k ][ j ]
					        || distance[ i ][ j ] == -1 ) {
						distance[ i ][ j ] = distance[ i ][ k ] + distance[ k ][ j ];
					}
				}
			}
		}
	}
}

int main( ) {
	int i, j, k;
	int N, M;
	long long temp;
	scanf("%d %d\n", &N, &M );
	for ( i = 1; i <= N; i++ ) {
		for ( j = 1; j <= N; j ++ ) {
			distance[ i ][ j ] = -1;
		}
		distance[ i ][ i ] = 0;
	}
	for ( i = 1; i <= M; i ++ ) {
		scanf("%d %d %lld", &j, &k, &temp );
		if ( temp < distance[ j ][ k ] || distance[ j ][ k ] == -1 ) {
			distance[ j ][ k ] = temp;
			distance[ k ][ j ] = temp;
		}
	}
	floyd( N );
	for ( i = 1; i <= N; i ++ ) {
		temp = 0;
		for ( j = 1; j <= N; j ++ ) {
			temp += distance[ i ][ j ];
			temp %= MOD;
		}
		printf("%lld\n", temp ); //輸入的temp是01 02 03 04最短路徑的類加
	}
    //這題最後輸出 7 11 9 11
	return 0;
}