代码随想录算法训练营第五十八天｜拓扑排序精讲 、dijkstra（朴素版）精讲

拓扑排序

117. 软件构建

from collections import deque, defaultdictdef topological_sort(n, edges):inDegree = [0] * n # inDegree 记录每个文件的入度umap = defaultdict(list) # 记录文件依赖关系# 构建图和入度表for s, t in edges:inDegree[t] += 1umap[s].append(t)# 初始化队列，加入所有入度为0的节点queue = deque([i for i in range(n) if inDegree[i] == 0])result = []while queue:cur = queue.popleft()  # 当前选中的文件result.append(cur)for file in umap[cur]:  # 获取该文件指向的文件inDegree[file] -= 1  # cur的指向的文件入度-1if inDegree[file] == 0:queue.append(file)if len(result) == n:print(" ".join(map(str, result)))else:print(-1)if __name__ == "__main__":n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]topological_sort(n, edges)

dijkstra（朴素版）

def dijkstra(grid, start, end, n):min_dist = [float('inf')] * (n + 1)visited = [False] * (n + 1)parent = [-1] * (n + 1)min_dist[start] = 0for _ in range(1, n):min_val = float('inf')cur = 1for v in range(1, n + 1):if not visited[v] and min_dist[v] < min_val:min_val = min_dist[v]cur = vvisited[cur] = Truefor v in range(1, n + 1):if (not visited[v] andgrid[cur][v] != float('inf') andmin_dist[cur] + grid[cur][v] < min_dist[v]):min_dist[v] = min_dist[cur] + grid[cur][v]parent[v] = cur# 打印最短路径path = [end]while parent[path[-1]] != -1:path.append(parent[path[-1]])path.reverse()for i in range(len(path) - 1):print(f"{path[i]} -> {path[i + 1]}")def main():n, m = map(int, input().split())grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]for _ in range(m):p1, p2, val = map(int, input().split())grid[p1][p2] = valstart = 1end = ndijkstra(grid, start, end, n)if __name__ == "__main__":main()