我想让节点 Arad 从出发，需要分别到达 Pitesti、Neamt、Eforie 三个节点（无先后顺序），步数应尽可能少，代价应尽可能低。
目前我的程序已经先写完了，但是运行的时候会随机出来两个结果：
第一个结果（正确结果）：Shortest path: ['Arad', 'Timisoara', 'Drobeta', 'Pitesti', 'Urziceni', 'Bucharest', 'Eforie', 'Bucharest', 'Hirsova', 'Neamt']
Shortest path cost: 127
但是Shortest path cost:的结果是错误的，正确结果应该是87
第二个结果（错误结果，Shortest path和hortest path cost均错误）：Shortest path: ['Arad', 'Sibiu', 'Fagaras', 'Rimnicu Vilcea', 'Neamt', 'Hirsova', 'Bucharest', 'Eforie', 'Bucharest', 'Urziceni', 'Pitesti']
Shortest path cost: 127
应该如何修改我的程序呢
我的程序如下：
import heapq
import itertools
def calculate_distances(graph, starting_vertex, targets):
distances = {vertex: (float('infinity'), None) for vertex in graph}
distances[starting_vertex] = (0, starting_vertex)
priority_queue = [(0, starting_vertex)]
visited = set()
visited_targets = targets.copy() # Copy the targets to operate on
while priority_queue and visited_targets:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_vertex in visited_targets:
visited_targets.remove(current_vertex)
if current_vertex in visited:
continue
visited.add(current_vertex)
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor][0]:
distances[neighbor] = (distance, current_vertex)
heapq.heappush(priority_queue, (distance, neighbor))
return distances
def find_path(distances, target, starting_vertex):
path = []
cost = distances[target][0]
while target is not None and target != starting_vertex:
path.append(target)
target = distances[target][1]
path.append(starting_vertex) # Add the starting vertex at the end
return path[::-1], cost
def find_shortest_path(graph, starting_vertex, targets):
min_path = None
min_cost = float('infinity')
# Generate all permutations of the targets
for permutation in itertools.permutations(targets):
total_cost = 0
current_vertex = starting_vertex
path = [starting_vertex]
# Calculate the total cost of visiting the targets in the current permutation
for target in permutation:
distances = calculate_distances(graph, current_vertex, {target})
segment_path, segment_cost = find_path(distances, target, current_vertex)
total_cost += segment_cost
current_vertex = target
# Add the segment path except the starting vertex to avoid duplicates
path.extend(segment_path[1:])
# Calculate the cost of returning to the starting vertex
distances = calculate_distances(graph, current_vertex, {starting_vertex})
return_path, return_cost = find_path(distances, starting_vertex, current_vertex)
total_cost += return_cost
# Check if the current permutation has the lowest cost
if total_cost < min_cost:
min_cost = total_cost
min_path = path
return min_path, min_cost
graph = {
'Arad': {'Zerind': 15, 'Sibiu': 10, 'Timisoara': 12},
'Zerind': {'Arad': 15, 'Oradea': 15, 'Sibiu': 8},
'Oradea': {'Zerind': 15, 'Fagaras': 7, 'Iasi': 9},
'Iasi': {'Oradea': 9, 'Neamt': 15, 'Vaslui': 18},
'Vaslui': {'Iasi': 18, 'Neamt': 13, 'Eforie': 16, 'Glurgiu': 9},
'Eforie': {'Vaslui': 16, 'Glurgiu': 7, 'Bucharest': 8, 'Connecticut': 18},
'Connecticut': {'Eforie': 18, 'Bucharest': 9, 'Craiova': 19},
'Craiova': {'Drobeta': 11, 'Pitesti': 12, 'Bucharest': 15, 'Connecticut': 19},
'Drobeta': {'Craiova': 11, 'Pitesti': 13, 'Mehadia': 7, 'Lugoj': 8, 'Timisoara': 13},
'Timisoara': {'Arad': 12, 'Lugoj': 8, 'Drobeta': 13},
'Sibiu': {'Zerind': 8, 'Arad': 10, 'Lugoj': 11, 'Fagaras': 10},
'Fagaras': {'Sibiu': 10, 'Oradea': 7, 'Rimnicu Vilcea': 9, 'Lugoj': 12, 'Atlanta': 12},
'Rimnicu Vilcea': {'Fagaras': 9, 'Neamt': 11, 'Urziceni': 14, 'Atlanta': 6},
'Neamt': {'Rimnicu Vilcea': 11, 'Iasi': 15, 'Vaslui': 13, 'Hirsova': 11},
'Hirsova': {'Neamt': 11, 'Glurgiu': 10, 'Bucharest': 8, 'Urziceni': 13},
'Glurgiu': {'Hirsova': 10, 'Eforie': 7, 'Vaslui': 9},
'Lugoj': {'Timisoara': 8, 'Mehadia': 11, 'Fagaras': 12, 'Sibiu': 11, 'Atlanta': 7, 'Urziceni': 16, 'Drobeta': 8},
'Atlanta': {'Lugoj': 7, 'Fagaras': 4, 'Rimnicu Vilcea': 6, 'Urziceni': 8},
'Urziceni': {'Atlanta': 8, 'Rimnicu Vilcea': 14, 'Hirsova': 13, 'Bucharest': 7, 'Lugoj': 16, 'Pitesti': 7},
'Bucharest': {'Urziceni': 7, 'Hirsova': 8, 'Eforie': 8, 'Craiova': 15, 'Pitesti': 15, 'Connecticut': 9},
'Pitesti': {'Bucharest': 15, 'Craiova': 12, 'Drobeta': 13, 'Mehadia': 10, 'Urziceni': 7},
'Mehadia': {'Drobeta': 7, 'Lugoj': 11, 'Pitesti': 10}
}
targets = {'Pitesti', 'Neamt', 'Eforie'}
starting_vertex = 'Arad'
distances = calculate_distances(graph, starting_vertex, targets.copy())
total_cost = 0
paths = {}
for target in targets:
path, cost = find_path(distances, target, starting_vertex)
paths[target] = path
total_cost += cost
shortest_path, shortest_path_cost = find_shortest_path(graph, starting_vertex, targets)
print("Shortest path:", shortest_path)
print("Shortest path cost:", shortest_path_cost)
