Pathfinding and payment delivery

Last lesson Alice read the map. Now she must pick a route. The sender picks the whole route in Lightning, not the network, and it has to work without knowing anyone's balances.

A shortest-path problem, with a twist

Think of each channel direction as a road with a toll, the routing fee. Finding the cheapest route is a classic shortest-path problem, and Dijkstra's algorithm solves it: always extend the cheapest path found so far until you reach the destination.

The twist: the map shows capacity, not liquidity. The cheapest route on paper may fail because a channel lacks balance on the right side.

Write the route finder

The starter turns Alice's graph into a list of neighbours with fee policies. Fill in find_route with Dijkstra, using heapq:

⚡Find the cheapest route

Python

NodeAlice · LNDBob · c-lightningChan · c-lightningDina · LNDNo node

import heapq from jifunze_lab import lnd def fee_msat(policy: dict, amount_msat: int) -> int: base = int(policy.get("fee_base_msat", 0)) rate = int(policy.get("fee_rate_milli_msat", 0)) return base + amount_msat * rate // 1_000_000 def edges_from(graph: dict) -> dict: """pubkey -> list of (neighbour pubkey, policy for sending from pubkey).""" out: dict = {} for e in graph["edges"]: for a, b, pol in ((e["node1_pub"], e["node2_pub"], e.get("node1_policy")), (e["node2_pub"], e["node1_pub"], e.get("node2_policy"))): if pol and not pol.get("disabled"): out.setdefault(a, []).append((b, pol)) return out def find_route(graph: dict, source: str, target: str, amount_msat: int) -> list[str]: """Return the list of pubkeys from source to target with the lowest total fee.""" # TODO: Dijkstra. Start with heap = [(0, source, [source])] and pop the cheapest path each time. return [] alice = lnd("alice") graph = alice.graph() dina = lnd("dina").pubkey names = {n["pub_key"]: n.get("alias") for n in graph["nodes"]} route = find_route(graph, alice.pubkey, dina, 10_000_000) print(" -> ".join(names.get(p, p[:8]) for p in route))

▶ RunCheckReset lessonRestore starter code

These exercises need a laptop with the lab running. You can read the lesson on your phone.

In the lab there is only one path, Alice → Bob → Chan → Dina, but your function is tested to make sure every step follows a real channel.

How real nodes do better

• Probabilistic cost. Besides fees, nodes score how likely each channel is to have enough balance. Bigger channels relative to the amount look safer.
• Mission control. When an attempt fails, the error says which channel failed. The node remembers and avoids it for a while, then retries. (You'll use this in lesson 16.)
• Multipart payments (MPP). A large payment can be split into several smaller parts over different routes, each more likely to fit. Dina only releases the preimage once every part has arrived.