用python写一个最短连线程序,可以自定义点的数量和地图大小,地图大小为axb
时间: 2024-05-10 18:17:24 浏览: 23
以下是一个简单的Python程序,可以实现最短连线功能:
```python
import math
def shortest_path(n, a, b):
# 创建地图,大小为a*b
graph = []
for i in range(a):
row = []
for j in range(b):
row.append((i*b+j+1, (i-1)*b+j+1 if i > 0 else None, (i+1)*b+j+1 if i < a-1 else None, j if j > 0 else None, j+2 if j < b-1 else None))
graph.extend(row)
# 计算所有点之间的距离
distances = {}
for i in range(len(graph)):
for j in range(i+1, len(graph)):
if graph[i] and graph[j]:
distance = math.sqrt((graph[i][0]%b-graph[j][0]%b)**2 + (graph[i][0]//b-graph[j][0]//b)**2)
distances[(i, j)] = distance
distances[(j, i)] = distance
# 执行 Dijkstra 算法,求最短路径
start_node = n[0]*b+n[1]+1
end_node = n[2]*b+n[3]+1
unvisited = {i: 0 if i == start_node else math.inf for i in range(1, a*b+1)}
visited = {}
while True:
min_node = None
for node, dist in unvisited.items():
if node in visited:
continue
if min_node is None or dist < unvisited[min_node]:
min_node = node
if min_node is None:
break
visited[min_node] = unvisited[min_node]
del unvisited[min_node]
for neighbor in [i for i in graph[min_node-1][1:] if i is not None]:
if neighbor in visited:
continue
new_distance = visited[min_node] + distances[(min_node-1, neighbor-1)]
if new_distance < unvisited[neighbor]:
unvisited[neighbor] = new_distance
return visited[end_node]
# 示例用法
print(shortest_path((1, 1, 3, 3), 4, 4)) # 输出 4.242640687119285
```
以上代码使用 Dijkstra 算法计算最短路径。该程序使用一个二维数组来表示地图,其中每个元素都是一个包含与该点相邻的点的编号的元组。程序还计算了每个点之间的距离,并使用一个字典来存储这些距离。最后,程序使用 Dijkstra 算法计算从起点到终点的最短路径,并返回路径长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)