Practice: Planning the Cheapest Ferry Crossings

import heapq
import math

H = ["Ardle", "Brack", "Colm", "Dunn", "Esk", "Fell"]
FARES = [("Ardle", "Brack", 3), ("Ardle", "Colm", 6), ("Brack", "Dunn", 4), ("Colm", "Dunn", 2),
         ("Colm", "Esk", 7), ("Dunn", "Esk", 2), ("Dunn", "Fell", 6), ("Esk", "Fell", 3)]


def dijkstra(edges):
    graph = {h: [] for h in H}
    for u, v, w in edges:
        graph[u].append((v, w))
    dist = {h: math.inf for h in H}
    prev = {h: "-" for h in H}
    rnd = {}
    dist["Ardle"] = 0
    settled, queue = set(), [(0, "Ardle")]
    while queue:
        _, u = heapq.heappop(queue)
        if u in settled:
            continue
        settled.add(u)
        rnd[u] = len(settled)
        for v, w in graph[u]:
            if v not in settled and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(queue, (dist[v], v))
    return dist, prev, rnd


def bellman_ford(edges):
    dist = {h: math.inf for h in H}
    prev = {h: "-" for h in H}
    dist["Ardle"] = 0
    for _ in range(len(H) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    cycle = any(dist[u] + w < dist[v] for u, v, w in edges)
    return dist, prev, cycle


d, p, r = dijkstra(FARES)
for h in H:
    print(f"{h} | {d[h]} | round {r[h]} | {p[h]}")
rebate = FARES + [("Colm", "Brack", -4)]
d2, _, _ = dijkstra(rebate)
b, bp, cycle = bellman_ford(rebate)
print("with Colm->Brack -4, dijkstra:     ", ", ".join(f"{h} {d2[h]}" for h in H))
print("with Colm->Brack -4, bellman-ford: ", ", ".join(f"{h} {b[h]}" for h in H), "| negative cycle:", cycle)
print("bellman-ford, harbour before each:", ", ".join(f"{h} {bp[h]}" for h in H))