用python写一个最短连线程序,可以自定义点的数量和地图大小
时间: 2024-05-09 15:15:44 浏览: 11
下面是一个Python实现的最短连线程序,可以自定义点的数量和地图大小。这个程序使用了Prim算法来生成最小生成树,然后使用Dijkstra算法来找到最短路径。
```python
import random
import math
import heapq
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
class Edge:
def __init__(self, a, b, weight):
self.a = a
self.b = b
self.weight = weight
def distance(p1, p2):
return math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
def generate_points(num_points, map_size):
points = []
for i in range(num_points):
x = random.randint(0, map_size)
y = random.randint(0, map_size)
points.append(Point(x, y))
return points
def generate_edges(points):
edges = []
for i in range(len(points)):
for j in range(i + 1, len(points)):
distance_between_points = distance(points[i], points[j])
edges.append(Edge(i, j, distance_between_points))
return edges
def prim(points):
visited = [False] * len(points)
visited[0] = True
heap = []
for edge in generate_edges(points):
if edge.a == 0:
heapq.heappush(heap, (edge.weight, edge))
while heap:
weight, edge = heapq.heappop(heap)
if visited[edge.b]:
continue
visited[edge.b] = True
yield edge
for next_edge in generate_edges(points):
if next_edge.a == edge.b and not visited[next_edge.b]:
heapq.heappush(heap, (next_edge.weight, next_edge))
def dijkstra(start, end, edges):
distances = [float('inf')] * len(edges)
distances[start] = 0
heap = [(0, start)]
while heap:
current_distance, current_vertex = heapq.heappop(heap)
if current_vertex == end:
return current_distance
if current_distance > distances[current_vertex]:
continue
for edge_index in range(len(edges)):
if edges[edge_index].a == current_vertex:
next_vertex = edges[edge_index].b
distance = edges[edge_index].weight
total_distance = current_distance + distance
if total_distance < distances[next_vertex]:
distances[next_vertex] = total_distance
heapq.heappush(heap, (total_distance, next_vertex))
return float('inf')
def shortest_path(points):
edges = list(prim(points))
total_distance = sum(edge.weight for edge in edges)
shortest_distance = float('inf')
for i in range(len(edges)):
edge = edges[i]
distance = dijkstra(edge.a, edge.b, edges[:i] + edges[i+1:])
if distance < shortest_distance:
shortest_distance = distance
return total_distance, shortest_distance
if __name__ == '__main__':
num_points = int(input("请输入点的数量:"))
map_size = int(input("请输入地图大小:"))
points = generate_points(num_points, map_size)
total_distance, shortest_distance = shortest_path(points)
print("生成的点:")
for point in points:
print("({}, {})".format(point.x, point.y))
print("最小生成树的总距离为:{}".format(total_distance))
print("最短路径的距离为:{}".format(shortest_distance))
```
这个程序使用了Prim算法来生成最小生成树,然后使用Dijkstra算法来找到最短路径。它首先生成一个包含指定数量的点的随机地图,然后计算最小生成树的总距离。接下来,它遍历所有可能的边,找到最短路径的距离。
你可以通过输入点的数量和地图大小来运行这个程序。