图论之弗洛伊德算法求解全源最短路径

news/2025/2/23 6:33:07

文章目录

题目
- 1334.阈值距离内邻居最少的城市

Floyd算法适合用于求解多源的最短路径的问题，相比之下，Dijkstra算法适合用于求解单源的最短路径的问题，并且，当边的权值只有1的时候，我们还能使用BFS求解最短路径的问题

图论之 BFS
图论之迪斯科特拉算法求解最短路径

灵神讲解

Floyd算法可以从递归中得到，相对应的，我们也有使用记忆化搜索和动态规划进行求解

递归方式的模版

@cache
def dfs(k,i,j):
	if k < 0:
		# w[i][j]为i到j的权值
		return w[i][j]
	return min(dfs(k-1,i,j),dfs(k-1,i,k)+dfs(k-1,k,j))

动态规划的模版

        # 首先构造图,无向图
        e = [[float('inf')]*n for _ in range(n)]
        for f,t,d in edges:
            e[f][t] = d 
            e[t][f] = d 

        # 三维数组，dp[k][i][j]表示从节点i到节点j并且中间结点<=k-1的最短距离(故意开多一个位置)
        dp = [[[0]*n for _ in range(n)] for _ in range(n+1)]
        # 初始化，dpp[0][i][j] = e[i][j]
        dp[0] = e[:]

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # 通过枚举找到最佳的情况
                    dp[k+1][i][j] = min(dp[k][i][j],dp[k][i][k]+dp[k][k][j])
# 最终的dp[n][i][j]就是所需的答案

题目

1334.阈值距离内邻居最少的城市

在这里插入图片描述

思路分析：我们直接使用Floyd算法进行求解即可

递归求解

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # 弗洛伊德算法其实就是递归就可以解决
        # 首先构造图,无向图
        e = [[float('inf')]*n for _ in range(n)]
        for f,t,d in edges:
            e[f][t] = d 
            e[t][f] = d 
        
        # 定义求解的弗洛伊德算法
        @cache
        def dfs(k,i,j):
            if k < 0:
                return e[i][j]
            return min(dfs(k-1,i,j),dfs(k-1,i,k)+dfs(k-1,k,j))
        ans = 0
        cur = float('inf')
        # 开始调用
        for i in range(n):
            count = 0
            for j in range(n):
                if i != j and dfs(n-1,i,j) <= distanceThreshold:
                    count+=1
            # 更新
            if count <= cur:
                cur = count
                ans = i 
        return ans

动态规划，动态规划的效率高一点

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # 弗洛伊德算法其实就是递归就可以解决
        # 首先构造图,无向图
        e = [[float('inf')]*n for _ in range(n)]
        for f,t,d in edges:
            e[f][t] = d 
            e[t][f] = d 

        # 三维数组，dp[k][i][j]表示从节点i到节点j并且中间结点<=k-1的最短距离(故意开多一个位置)
        dp = [[[0]*n for _ in range(n)] for _ in range(n+1)]
        # 初始化，dpp[0][i][j] = e[i][j]
        dp[0] = e[:]

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # 通过枚举找到最佳的情况
                    dp[k+1][i][j] = min(dp[k][i][j],dp[k][i][k]+dp[k][k][j])
        
        ans = 0
        cur = float('inf')
        # 开始调用
        for i in range(n):
            count = 0
            for j in range(n):
                if i != j and dp[n][i][j] <= distanceThreshold:
                    count+=1
            # 更新
            if count <= cur:
                cur = count
                ans = i 
        return ans