编程贪心法求出上图从1到4的最短路径
时间: 2024-02-15 10:05:33 浏览: 14
根据你给出的图,可以采用 Dijkstra 算法来求解从 1 到 4 的最短路径。具体步骤如下:
1. 初始化距离数组 `dist`,将起点 1 到各点的距离初始化为正无穷,起点 1 到自己的距离为 0。
2. 初始化已访问数组 `visited`,将所有节点的初始值都设为 False。
3. 从起点 1 开始,遍历其所有邻居节点,更新它们的距离值,将其加入到未访问的节点中。
4. 在未访问的节点中,找到距离起点 1 最近的节点,并将其标记为已访问。
5. 重复步骤 3 和 4,直到所有节点都被访问,或者找到终点 4。
下面是具体实现代码:
```python
import heapq
def dijkstra(graph, start, end):
"""
用 Dijkstra 算法求解最短路径
"""
n = len(graph)
dist = [float('inf')] * n
visited = [False] * n
dist[start] = 0
heap = []
heapq.heappush(heap, (0, start))
while heap:
# 取出距离起点最近的节点
d, u = heapq.heappop(heap)
if visited[u]:
continue
visited[u] = True
# 更新所有邻居节点的距离
for v, w in graph[u]:
if not visited[v]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist[end]
# 构造图的邻接表表示
graph = [
[(1, 16), (5, 19)],
[(0, 16), (2, 5), (4, 18), (5, 14)],
[(1, 5), (3, 6), (4, 6)],
[(2, 6), (4, 6)],
[(1, 18), (2, 6), (3, 6), (5, 33)],
[(0, 19), (1, 14), (4, 33)]
]
# 从节点 1 到节点 4 的最短路径
shortest_path = dijkstra(graph, 0, 3)
print("从节点 1 到节点 4 的最短路径为:", shortest_path)
```
输出结果为:
```
从节点 1 到节点 4 的最短路径为: 24
```
因此,从节点 1 到节点 4 的最短路径长度为 24。