Python graphs

A graph is places (nodes) joined by edges. Keep it as a dictionary of neighbours: graph[a] is the list of nodes next to a.

Breadth-first search, with a queue, finds the shortest path when every step costs the same; Dijkstra's algorithm, with a heap, when steps cost different amounts.

from collections import deque
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
dist = {1: 0}
queue = deque([1])
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in dist:
            dist[nxt] = dist[node] + 1
            queue.append(nxt)
print(dist[4])

Watch for: Mark a node as seen when you add it to the queue, not when you take it out, or it is added many times.