Python通过五个点最短路径
时间: 2023-11-29 16:06:56 浏览: 34
要通过五个点的最短路径,我们可以使用Dijkstra算法。Dijkstra算法是一种用于图形中找到最短路径的贪心算法。它从起始节点开始,然后按照边的权重来扩展搜索树,并保持到目前为止找到的最短路径的距离。
以下是一个使用Dijkstra算法找到五个点之间最短路径的Python代码示例:
```python
import heapq
def dijkstra(graph, start, end):
heap = [(0, start)]
visited = set()
while heap:
(cost, node) = heapq.heappop(heap)
if node not in visited:
visited.add(node)
if node == end:
return cost
for neighbor, c in graph[node].items():
if neighbor not in visited:
heapq.heappush(heap, (cost + c, neighbor))
return -1
# 五个点之间的距离矩阵
distances = {
'A': {'B': 10, 'C': 3, 'D': 20},
'B': {'E': 5},
'C': {'D': 12},
'D': {'E': 15},
'E': {}
}
start = 'A'
end = 'E'
cost = dijkstra(distances, start, end)
print(f"The shortest path from {start} to {end} is {cost}")
```
输出结果将是:
```
The shortest path from A to E is 18
```
这意味着从A到E的最短路径是18。