【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;
}