44 lines
1.0 KiB
Python
44 lines
1.0 KiB
Python
class DijkstraStats:
|
|
def __init__(self):
|
|
self.extract_min_calls = 0
|
|
self.relax_attempts = 0
|
|
self.relax_success = 0
|
|
# self.decrease_key_calls = 0
|
|
# self.add_calls = 0
|
|
|
|
def heap_dijkstra(nodes, adj, heap, start):
|
|
INF = float('inf')
|
|
dist = [INF] * nodes
|
|
visited = [False] * nodes
|
|
stats = DijkstraStats()
|
|
|
|
dist[start] = 0
|
|
|
|
for v in range(nodes):
|
|
heap.add(v, dist[v])
|
|
# stats.add_calls += 1
|
|
|
|
while True:
|
|
res = heap.extract_min()
|
|
stats.extract_min_calls += 1
|
|
if res is None:
|
|
break
|
|
cur, cur_dist = res
|
|
|
|
if cur_dist == INF:
|
|
break
|
|
|
|
for nxt, d in adj[cur]:
|
|
stats.relax_attempts += 1
|
|
if visited[nxt]:
|
|
continue
|
|
new = cur_dist + d
|
|
if new < dist[nxt]:
|
|
stats.relax_success += 1
|
|
dist[nxt] = new
|
|
heap.decrease_key(nxt, new)
|
|
|
|
visited[cur] = True
|
|
|
|
# return dist, stats
|
|
return stats |