代码随想录算法训练营DAY64｜拓扑排序、dijkstra（质朴版） ...

拓扑排序精讲

1. from collections import deque
3. def bfs(degrees):
4.     nodes = deque()
5.     for j in range(n):
6.         if degrees[j]==0:
7.             nodes.append(j)
9.     result = []        
10.     while nodes:
11.         idx = nodes.popleft()
12.         result.append(str(idx))
13.         if depend[idx]:
14.             for file in depend[idx]:
15.                 degrees[file]-=1
16.                 if degrees[file]==0:
17.                     nodes.append(file)
19.     if len(result)==n:
20.         print((' ').join(result))
21.     else:
22.         print(-1)
23.             
24.             
25. if __name__=="__main__":
26.     n,m = map(int, input().split())
27.     degrees = [0]*n
28.     depend = [[] for _ in range(n)]
29.     for i in range(m):
30.         a,b = map(int, input().split())
31.         depend[a].append(b)
32.         degrees[b]+=1
33.     bfs(degrees)

复制代码

dijkstra（质朴版）精讲

1. def dijkstra(graph, n):
2.     min_dist = [float('inf')]*n
3.     visited = [False]*n
4.    
5.     min_dist[0]=0
6.     for i in range(n):
7.         min_val = float('inf')
8.         cur = -1
9.         for j in range(n):
10.             if not visited[j] and min_dist[j]<min_val:
11.                 min_val = min_dist[j]
12.                 cur = j
13.         visited[cur]=True
14.         
15.         for k in range(n):
16.             if not visited[j] and min_dist[cur]+graph[cur][k]<min_dist[k]:
17.                 min_dist[k]=graph[cur][k]+min_dist[cur]
18.    
19.     if min_dist[-1] == float('inf'):
20.         print(-1)
21.     else:
22.         print(min_dist[-1])
23.         
24. if __name__=='__main__':
25.     n,m = map(int, input().split())
26.     graph = [[float('inf')]*n for _ in range(n)]
27.     for i in range(m):
28.         s,e,v = map(int, input().split())
29.         graph[s-1][e-1]=v
30.    
31.     dijkstra(graph, n)  

复制代码

prim和dijkstra的区别

• prim是求非访问节点到最小生成树的最小距离，而dijkstra是求非访问节点到源点的最小距离。
  
• prim算法可以有负权值，dijkstra算法不可以有负权值
  
• prim 更新 minDist数组的写法：
  

1. for (int j = 1; j <= v; j++) {
2.     if (!isInTree[j] && grid[cur][j] < minDist[j]) {
3.         minDist[j] = grid[cur][j];
4.     }
5. }

复制代码

• dijkstra 更新 minDist数组的写法：
  

1. for (int v = 1; v <= n; v++) {
2.     if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
3.         minDist[v] = minDist[cur] + grid[cur][v];
4.     }
5. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。