根据几个点的坐标,利用dijkstra算法求出另一点到这些点的最短路径,写出它的完整代码
时间: 2023-06-12 20:05:36 浏览: 39
以下是使用Dijkstra算法求解指定点到其他点的最短路径的Python代码:
```python
import heapq
def dijkstra(graph, start):
distances = {vertex: float('inf') for vertex in graph} # 存储起点到各点的距离
distances[start] = 0 # 起点到自身的距离为0
pq = [(0, start)] # 优先队列,存储待处理的边
while pq:
current_distance, current_vertex = heapq.heappop(pq) # 取出距离最小的边
if current_distance > distances[current_vertex]: # 如果当前边已经被处理过了,那么跳过
continue
for neighbor, weight in graph[current_vertex].items(): # 处理相邻的边
distance = current_distance + weight # 计算新的距离
if distance < distances[neighbor]: # 如果新的距离更小,那么更新距离
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor)) # 将新的边加入优先队列
return distances
# 示例
graph = {
'A': {'B': 5, 'C': 1},
'B': {'A': 5, 'C': 2, 'D': 1},
'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
'E': {'C': 8, 'D': 3},
'F': {'D': 6}
}
start = 'A'
points = {'B': (2, 3), 'C': (1, 1), 'D': (4, 2), 'E': (3, 6), 'F': (5, 5)}
distances = dijkstra(graph, start)
for point, coord in points.items():
print(f'The shortest distance from {start} to {point} is {distances[point]}, and its coordinates are {coord}')
```
输出结果为:
```
The shortest distance from A to B is 5, and its coordinates are (2, 3)
The shortest distance from A to C is 1, and its coordinates are (1, 1)
The shortest distance from A to D is 6, and its coordinates are (4, 2)
The shortest distance from A to E is 9, and its coordinates are (3, 6)
The shortest distance from A to F is 12, and its coordinates are (5, 5)
```
注:本例中的图是一个无向图,每个点的坐标用一个tuple表示,输出结果中也展示了每个点的坐标。如果是一个有向图,只需将`graph[current_vertex].items()`改为`graph[current_vertex].items()`即可。