选课次序代码Dijkstra算法
时间: 2023-10-04 21:12:41 浏览: 42
选课次序可以看作是一个有向无环图(DAG),其中每个节点表示一个课程,每条边表示先修关系,即一门课程必须在另一门课程之前修完。
Dijkstra算法是一种单源最短路径算法,但是它只适用于没有负权边的图。在选课次序问题中,我们可以将每条边的权重都看作为1,表示先修关系的存在。
具体实现如下:
1. 对于所有的节点,初始化距离dist为无穷大,起点的距离设为0。
2. 将起点加入到一个优先队列中,每次从队列中取出距离最小的节点u。
3. 遍历节点u的所有出边,对于每个邻居节点v,如果起点到v的距离比起点到u再加上边权更短,则更新v的距离dist,并将v加入到优先队列中。
4. 重复步骤2和3,直到队列为空。
5. 最终得到的dist数组就是每个节点到起点的最短距离,也就是选课的最小次序。
代码实现如下(假设节点编号从0开始):
```python
import heapq
def course_order(n, edges):
# 初始化距离
dist = [float('inf') for _ in range(n)]
dist[0] = 0
# 构建邻接表
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
# Dijkstra算法
pq = [(0, 0)] # (距离, 节点编号)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v in adj[u]:
if dist[v] > dist[u] + 1:
dist[v] = dist[u] + 1
heapq.heappush(pq, (dist[v], v))
return dist
```
其中,n表示节点个数,edges是一个包含所有边信息的列表,每个元素是一个二元组(u, v),表示从节点u到节点v有一条有向边。函数返回值是一个长度为n的列表,表示每个节点到起点的最短距离。