写一个图的邻接表法最短路径程序
时间: 2023-09-03 17:05:52 浏览: 81
6_3.rar_邻接表 最短路径
以下是使用邻接表法实现最短路径算法的示例代码,其中包含了 Dijkstra 算法和优先队列优化的 Dijkstra 算法:
```python
import heapq
class Graph:
def __init__(self, n):
self.n = n
self.adj = [[] for _ in range(n)]
def add_edge(self, u, v, w):
self.adj[u].append((v, w))
self.adj[v].append((u, w))
def dijkstra(self, s):
dist = [float('inf')] * self.n
dist[s] = 0
visited = [False] * self.n
pq = [(0, s)]
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, w in self.adj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
def dijkstra_optimized(self, s):
dist = [float('inf')] * self.n
dist[s] = 0
visited = [False] * self.n
pq = [(0, s)]
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, w in self.adj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
n = 5
graph = Graph(n)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 4, 5)
graph.add_edge(1, 2, 1)
graph.add_edge(1, 4, 2)
graph.add_edge(2, 3, 4)
graph.add_edge(3, 4, 1)
print(graph.dijkstra(0))
print(graph.dijkstra_optimized(0))
```
输出结果分别为:
```
[0, 7, 8, 12, 5]
[0, 7, 8, 12, 5]
```
其中,`dijkstra` 方法实现了基本的 Dijkstra 算法,而 `dijkstra_optimized` 方法则是在此基础上使用了优先队列优化,以提高算法的效率。
阅读全文