Dijkstra's algorithm

The shortest route from one place to every other. It repeats:

Finish the closest unfinished place.
Check each road out of it, and update any neighbor it gets to faster.

Run this first.

pie.clear()
pie.scalar(0, out='gridOpacity')
import numpy as np
gray, ink, orange, blue, purple, red = '#78716c', '#1c1917', '#ea580c', '#1d4ed8', '#7e22ce', '#dc2626'
spots = {'A': (-4, 0), 'B': (-2.5, 2.5), 'C': (-2, -2), 'D': (0, 0.8), 'E': (0.3, -2.8),
         'F': (1.5, 3), 'G': (2.2, -0.8), 'H': (4, 1.5), 'I': (4, -2.5)}
roads = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('B', 'F'), ('D', 'F'), ('D', 'G'),
         ('C', 'E'), ('E', 'G'), ('F', 'H'), ('G', 'H'), ('G', 'I'), ('E', 'I')]
points = {k: pie.point(x, y, fill=ink) for k, (x, y) in spots.items()}

def road_length(p, q):
    """The distance from p to q, rounded."""
    return round(float(np.hypot(q[0] - p[0], q[1] - p[1])), 1)

def label(p, q):
    return f'{road_length(p, q)}'

def label_spot(p, q, side):
    """The x (side 0) or y (side 1) of a spot a little to the side of the middle of the road from p to q."""
    normal = np.array([p[1] - q[1], q[0] - p[0]]) / (np.hypot(q[0] - p[0], q[1] - p[1]) or 1)
    return (p[side] + q[side]) / 2 + 0.25 * normal[side]

def shifted(p, side, by):
    """The x (side 0) or y (side 1) of point p, plus `by`."""
    return p[side] + by

where = {}
def track(*ps):
    """Keeps `where` up to date with every place's position. Lifted, so it reruns whenever a place moves."""
    where.update(zip(spots, ps))
    return 0

text_of = pie.lift(label, str)
spot_of = pie.lift(label_spot, pie.Scalar)
shift = pie.lift(shifted, pie.Scalar)
pie.lift(track, pie.Scalar)(*points.values())
lines, lengths = {}, {}
for u, v in roads:
    p, q = points[u], points[v]
    lines[u, v] = lines[v, u] = pie.line(p, q, stroke=gray)
    lengths[u, v] = lengths[v, u] = pie.text(text_of(p, q), spot_of(p, q, 0), spot_of(p, q, 1), 10, stroke=gray)
# Each place's letter goes below it, and its distance above it.
names = {k: pie.text(k, shift(p, 0, 0), shift(p, 1, -0.4), 14, stroke=ink) for k, p in points.items()}
dist_spot = {k: (shift(p, 0, 0), shift(p, 1, 0.5)) for k, p in points.items()}

def badge(k, value, color):
    """Writes place k's distance in a box above it."""
    pie.text(value, *dist_spot[k], 12, -1, -1, stroke=color, out=f'dist{k}')

for k in spots:
    badge(k, '∞', purple)

Then run the algorithm. You can drag the points to change the edge lengths and then run it again:

start, end = 'A', 'I'
# Back to the starting colors, in case this ran before.
pie.set_stroke(list(lines.values()) + list(lengths.values()), gray)
pie.set_stroke(list(names.values()), ink)
pie.set_fill(list(points.values()), ink)
tick = pie.scalar(0)  # not drawn; animating it is a half-second pause

def pause(halves=1):
    for _ in range(halves):
        pie.translate_scalar_by(tick, 1, animate=True)

def say(message):
    pie.text(message, 0, -4.8, 13, stroke=ink, out='status')

def fmt(d):
    return '∞' if d == np.inf else f'{d:.1f}'

def count():
    pie.text(f'finished: {len(done)}, roads checked: {checks}', 0, 4.8, 14, stroke=ink, out='count')

# The road lengths as they are now. Dragging during the run changes the labels, not this run.
length = {k: {} for k in spots}
for u, v in roads:
    length[u][v] = length[v][u] = road_length(where[u], where[v])
dist = {k: np.inf for k in spots}
came = {}  # came[v]: the place before v on the shortest route to v found so far
done = set()
checks = 0

for k in spots:
    badge(k, '∞', purple)
dist[start] = 0
badge(start, fmt(0), purple)
count()
say(f'start at {start}, distance 0')
pause(2)
while True:
    left = [k for k in spots if k not in done and dist[k] < np.inf]
    if not left:
        break
    # Step 1: the unfinished place with the smallest distance.
    u = min(left, key=dist.get)
    ring = pie.circle(points[u], 0.3, stroke=orange, out='ring')
    done.add(u)
    pie.set_fill(points[u], blue)
    pie.set_stroke(names[u], blue)
    badge(u, fmt(dist[u]), blue)
    count()
    say(f'{u} has the smallest distance left, {fmt(dist[u])}, so it is final')
    pause(2)
    # Step 2: check each road out of it.
    for v, w in length[u].items():
        if v in done:
            continue
        checks += 1
        count()
        pie.set_stroke([lines[u, v], lengths[u, v]], orange)
        new = round(dist[u] + w, 1)
        shorter = new < dist[v]
        say(f'{u} to {v}: {fmt(dist[u])} + {w:.1f} = {new:.1f}, ' + ('shorter than' if shorter else 'not shorter than') + f' {fmt(dist[v])}')
        pause(2)
        if shorter:
            if v in came:
                pie.set_stroke(lines[came[v], v], gray)
            dist[v] = new
            came[v] = u
            badge(v, fmt(new), purple)
            pie.set_stroke(lines[u, v], blue)
        else:
            pie.set_stroke(lines[u, v], gray)
        pie.set_stroke(lengths[u, v], gray)
        pause()
pie.remove(ring)

# The shortest route from start to end, in red.
k = end
while k != start:
    pie.set_stroke(lines[came[k], k], red)
    k = came[k]
say(f'shortest route from {start} to {end}: {fmt(dist[end])}')

It only works when no road has a negative length.