leetcode每日一题 2642.设计可以求最短路径的图

题目详情

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。

请你实现一个 Graph 类：

• Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
• addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
• int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径 最小 代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

解题思路

DFS

DFS调用超过python最大默认深度1000。

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.graph_dict = {}
        for i in edges:
            if i[0] in self.graph_dict:
                temp = self.graph_dict[i[0]]
                temp.append(i[1:])
                self.graph_dict[i[0]] = temp
            else:
                self.graph_dict[i[0]] = [i[1:]]
    def addEdge(self, edge: List[int]) -> None:
        if edge[0] in self.graph_dict:
            temp = self.graph_dict[edge[0]]
            temp.append(edge[1:])
            self.graph_dict[edge[0]] = temp
        else:
            self.graph_dict[edge[0]] = [edge[1:]]
    

    def shortestPath(self, node1: int, node2: int) -> int:
        self.res = []
        if node1 not in self.graph_dict:
            return -1
        def dfs(s,t,c):
            if s == t:
                self.res.append(c)
                return
            if s not in self.graph_dict:
                return
            for ele in self.graph_dict[s]:
                c += ele[1]
                dfs(ele[0], t, c)
                c -= ele[1]
            return self.res
        
        dfs(node1,node2,0)
        if self.res == []:
            return -1
        else:
            return min(self.res)

# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)

Dijkstras

使用Dijkstra算法， 我们使用Dijkstra算法求节点node1到节点node2的最短路径，其中

dist[i]表示从节点node1到节点i的最短距离；

vis[i]表示节点i是否被访问过。

初始化：dist[node1] = 0,其余为正无穷，然后我们遍历n次，每次找到当前未被访问的节点t，使得dist[t]最小。然后我们将节点t标记为以访问，更新dist[i]的值为min(dist[i], dist[t] + gti),最后我们返回dist[node2]，如果dist[node2]为无穷大，那么就说明两节点之间不存在路径。

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.g = [[inf] * n for _ in range(n)]
        for f, t, c in edges:
            self.g[f][t] = c

    def addEdge(self, edge: List[int]) -> None:
        f, t, c = edge
        self.g[f][t] = c

    def shortestPath(self, node1: int, node2: int) -> int:
        dist = [inf] * self.n
        dist[node1] = 0
        vis = [False] * self.n
        for _ in range(self.n):
            t = -1
#找到一个没有遍历的点
            for j in range(self.n):
                if not vis[j] and (t == -1 or dist[t] > dist[j]):
                    #not vis[j]表示节点 j 尚未被访问过
                    #t == -1表示没有找到更短的路径
                    #dist[t] > dist[j]表示找到了一条更短的路径
                    t = j
            vis[t] = True
            for j in range(self.n):
                dist[j] = min(dist[j], dist[t] + self.g[t][j])
        return -1 if dist[node2] == inf else dist[node2]