我目前正在嘗試制作一種演算法，當所有節點都被訪問時，它可以為我提供圖形的總成本，但我卻慘遭失敗，老實說，出于想法。我的目標是使用 Dijkstra 演算法獲得下圖的總成本。
這是我到目前為止所擁有的：
from collections import defaultdict
import heapq
def build_graph():
# Create the graph with the all given nodes and costs
edges = aeroDistances
graph = defaultdict(dict)
for edge in edges.items():
tuple1 = edge[0][0]
tuple2 = edge[0][1]
cost = edge[1]
connection1 = {tuple2 : cost}
connection2 = {tuple1 : cost}
graph[tuple1].update(connection1)
graph[tuple2].update(connection2)
return dict(graph)
def dijkstra(graph, starting_vertex):
# All the distances set to infinity
distances = {vertex: float('infinity') for vertex in graph}
# Distance from the starting vertex
distances[starting_vertex] = 0
# Priority queue
pq = [(0, starting_vertex)]
while len(pq) > 0:
current_distance, current_vertex = heapq.heappop(pq)
# Nodes can get added to the priority queue multiple times. We only
# process a vertex the first time we remove it from the priority queue
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance weight
# Only consider this new path if it's better than any path we've
# already found
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances, distance
numCidades = 0
numAeroportos = 0
numEstradas = 0
#custoAeroportos = {}
#custoEstradas = {}
#custoAeroportos = {(1, 2): 2, (1, 3): 4}
#custoEstradas = {(3, 1, 'E'): 2}
#custoAeroportos = {(1, 2): 1, (2, 3): 2, (3, 4): 1, (4, 1): 1}
custoAeroportos = {(1, 2): 1, (1, 3): 6, (2, 4): 2, (3, 4): 2}
custoEstradas = {(2, 3): 3}
listCidades = [1,2,3]
distances = []
indexValue = 0
indexKey = 0
currentIndex = 0
# Deconstruct the dict into a list of keys (tuples)
# Deconstruct the dict into a list of values
# Make it easier to sort the connections by creating a list of tuples and
# their respective weights and zip them toghether
distancesAeroKeys = list(custoAeroportos.keys())
distancesAeroValues = list(custoAeroportos.values())
aeroDistances = dict(map(list, zip(*[distancesAeroKeys, distancesAeroValues])))
print()
print("AeroDistances: " str(aeroDistances))
graph = build_graph()
print()
print("Graph: " str(graph))
print()
print("Dijkstra: " str(dijkstra(graph, 1)))
我目前正在嘗試使用的兩個圖表，即custoAeroportos，當訪問所有節點時，我似乎無法獲得總最低成本。
這是圖表，它們相當簡單：
這個一共花費5
這個一共花費3
我得到的總成本是錯誤的，我無法弄清楚。
對于第一張圖：
AeroDistances: {(1, 2): 1, (1, 3): 6, (2, 4): 2, (3, 4): 2}
Graph: {1: {2: 1, 3: 6}, 2: {1: 1, 4: 2}, 3: {1: 6, 4: 2}, 4: {2: 2, 3: 2}}
Dijkstra: ({1: 0, 2: 1, 3: 5, 4: 3}, 7)
對于第二張圖，不知何故是正確的：
AeroDistances: {(1, 2): 1, (2, 3): 2, (3, 4): 1, (4, 1): 1}
Graph: {1: {2: 1, 4: 1}, 2: {1: 1, 3: 2}, 3: {2: 2, 4: 1}, 4: {3: 1, 1: 1}}
Dijkstra: ({1: 0, 2: 1, 3: 2, 4: 1}, 3)
我真的很感謝你的幫助，謝謝。
uj5u.com熱心網友回復：
您的函式回傳distance從起始頂點到添加到堆中的最后一個節點的路徑。這不是你真正想要回傳的。當然，當 BFS-tree 從某些頂點有多個出邊時，這條路徑與總距離關系不大。
相反，您需要累積“接受”的邊的權重，即那些（隱式）從堆中彈出的邊，并提高該節點的距離。
因此，我建議使用更多資訊擴展堆上的元組：將我們帶到該節點的最后一條邊的權重。當節點被接受時，這條邊成為生成樹的一部分，然后它的權重應該被添加到一個累計總數中。
這是改編后的代碼。這些變化有伴隨的評論：
def dijkstra(graph, starting_vertex):
distances = {vertex: float('infinity') for vertex in graph}
distances[starting_vertex] = 0
graph_distance = 0 # this will be returned
pq = [(0, 0, starting_vertex)] # middle value is edge weight
while len(pq) > 0:
current_distance, edge_weight, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
graph_distance = edge_weight # accumulate
for neighbor, weight in graph[current_vertex].items():
distance = current_distance weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, weight, neighbor)) # include weight
return distances, graph_distance # ...return it
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400689.html
下一篇：創建24小時時間格式的方法