题目详情
给你一个有
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]] = tempelse: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]] = tempelse: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 -1def dfs(s,t,c):if s == t:self.res.append(c)returnif s not in self.graph_dict:returnfor ele in self.graph_dict[s]:c += ele[1]dfs(ele[0], t, c)c -= ele[1]return self.resdfs(node1,node2,0)if self.res == []:return -1else: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 = nself.g = [[inf] * n for _ in range(n)]for f, t, c in edges:self.g[f][t] = cdef addEdge(self, edge: List[int]) -> None:f, t, c = edgeself.g[f][t] = cdef shortestPath(self, node1: int, node2: int) -> int:dist = [inf] * self.ndist[node1] = 0vis = [False] * self.nfor _ 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 = jvis[t] = Truefor 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]
