单源最短路

[编程题]单源最短路

热度指数：13080 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径，返回 1 到 n 的最短路径值。如果 1 无法到 n ，输出 -1

图中可能有重边，无自环。

数据范围： $1 < n \le 500$ ， $1 \le m \le 5000$ ， $1 \le dist(n, m) \le 1000$

示例1

输入

5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]

输出

示例2

输入

2,1,[[1,2,4]]

输出

备注:

两个整数n和m,表示图的顶点数和边数。
一个二维数组，一维3个数据，表示顶点到另外一个顶点的边长度是多少
每条边的长度范围[0,1000]。
注意数据中可能有重边

算法知识视频讲解

Python 3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 顶点数
# @param m int整型 边数
# @param graph int整型二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
# @return int整型
#
class Solution:
    def findShortestPath(self , n: int, m: int, graph: List[List[int]]) -> int:
        # write code here
        min_dis = {}

        for i in range(m):
            source = graph[i][0]
            dest = graph[i][1]
            distance = graph[i][2]

            if (source, dest) in min_dis:
                min_dis[(source, dest)] = min(distance, min_dis[(source, dest)])
            else:
                min_dis[(source, dest)] = distance

        visited = set()
        visit = [1]
        min_dis[(1, 1)] = 0
        while len(visit) != 0:
            next_visit = []

            # 从 point 发散
            for point in visit:
                if point in visited:
                    continue
                else:
                    visited.add(point)

                # 统计发散
                for dest in range(2, n + 1):
                    if dest == point:
                        continue

                    # 有路径
                    if (point, dest) in min_dis:
                        next_visit.append(dest)
                        if (1, dest) in min_dis:
                            min_dis[(1, dest)] = min(min_dis[(1, dest)], min_dis[(1, point)] + min_dis[(point, dest)])
                        else:
                            min_dis[(1, dest)] = min_dis[(1, point)] + min_dis[(point, dest)]
            visit = next_visit
            

        if (1, n) not in min_dis:
            return -1
        return min_dis[(1, n)]

发表于 2024-05-19 22:32:25 回复(0)

Python 3

gapex

python3动态规划

from collections import defaultdict

class Solution:
    def findShortestPath(self , n , m , graph):
        nexts = defaultdict(list)
        for src, dst, w in graph:
            nexts[src].append((dst, w))
        dp = [None] * (n) + [0] # d[k]表示k到n的最短距离
        for i in range(n, 0, -1):
            if any(dp[j] is not None for j, _ in nexts[i]):
                dp[i] = min(dp[j] + w for j, w in nexts[i] if dp[j] is not None)
        return dp[1] if dp[1] else -1

发表于 2021-09-25 21:33:40 回复(0)

Python 3

Crawler201908052222442

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int 顶点数
# @param m int 边数
# @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
# @return int
#
class Solution:
    def findShortestPath(self, n, m, graph):
        # write code here

        headMap = dict()
        #         n = len(graph)
        points = dict()
        scores = [-1 for i in range(n+1)]
        paths = dict()
        matrix = [[-1 for j in range(n+1)] for i in range(n+1)]


        for g in graph:
            headMap[g[0]] = float("inf")
            headMap[g[1]] = float("inf")
            x, y = g[0], g[1]
            if x not in points:
                points[x] = []
            points[x].append(y)
            if matrix[x][y] == -1:
                matrix[x][y] = g[2]
            elif matrix[x][y] > g[2]:
                matrix[x][y] = g[2]

        paths[1] = None
        scores[1] = 0
        headMap[1] = 0

        while len(headMap) > 0:
            k = self.getSmallDict(headMap)

            scores[k] = headMap[k]
            headMap.pop(k)

            for p in points.get(k, []):
                if p in headMap :
                    if scores[k] + matrix[k][p] < headMap[p]:
                        paths[p] = k

                    headMap[p] = min(scores[k] + matrix[k][p], headMap[p])

        return scores[n]


    def getSmallDict(self, h):
        kk = 0
        value = float("inf")

        for k in h:
            if kk == 0:
                kk = k
            if h[k] < value:
                value = h[k]
                kk = k
        return kk

发表于 2021-09-04 18:51:53 回复(0)

Python 3

HHHChen77

python dfs找有向无环图路径

class Solution:
    def __init__(self):
        # 哈希表构造图中边信息
        self.map = {}
        # 记录最短路径长度
        self.result = float('INF')
    def findShortestPath(self , n , m , graph ):
        # 先构图
        for g in graph:
            if g[0] in self.map:
                # 重边保留最小的长度 注：长度上限为1000
                self.map[g[0]][g[1]] = min(g[2],self.map[g[0]].get(g[1],1001))
            else:
                self.map[g[0]] = {g[1]:g[2]}
        # 1为起点 n为终点
        self.dfs(1, n, 0)
        return self.result if self.result != float('INF') else -1
    # 深度优先遍历
    def dfs(self, start, end, val):
        if start == end:
            # 有效路径 记录最小值
            self.result = min(self.result, val)
            return
        # 不存在的结点即为无效路径
        if start not in self.map:
            return
        # 查找路径 即找start所有的下个结点
        for nex in self.map[start].keys():
            self.dfs(nex, end, val + self.map[start][nex])

python 动态规划

class Solution:
    def findShortestPath(self , n , m , graph ):
        # dp[i]定义为到达结点i的最小路径长度
        dp = [-1] * (n+1)
        # basecase 起点即终点
        dp[1] = 0
        # 状态转移
        for i in range(2, n+1):
            # 记录到达每个结点最小路径长度
            min_len = float('INF')
            # 遍历所有边信息
            for j in range(m):
                # 是否有边到达结点i 且 该边的起点是否可达
                if graph[j][1] == i and dp[graph[j][0]] != -1:
                    min_len = min(min_len, graph[j][2] + dp[graph[j][0]])
            # 判断是否有有效路径到达结点i
            if min_len != float('INF'):
                dp[i] = min_len
        # 返回到达终点n的最小路径长度
        return dp[n]

编辑于 2021-07-22 02:20:57 回复(0)