《打造自己的套利机器人》课程的辅助课。第 5 到第 8 课会把货币看作图。这里不用钱，改用地图来说明这个词。
图就是一张地图
想象一个小社区。里面有四个地点：Home（家）、Park（公园）、Cafe（咖啡馆）、Work（工作地点）。其中一些地点之间有道路，每条路都要花几分钟。
- Home 到 Cafe：4。Home 到 Park：2。Park 到 Cafe：1。Cafe 到 Work：5。Park 到 Work：8。
这些地点叫作节点（或顶点）。道路叫作边。道路所需的分钟数就是它的权重。合在一起就是一个图，没有更多含义。地铁图和社交网络也是图，汇率表同样如此：货币是节点，汇率是一条边。
存储图
对于每个节点，存储从它出发的道路列表。在 Python 中，这是一个由列表组成的字典：
roads = {("Home", "Cafe"): 4, ("Home", "Park"): 2, ("Park", "Cafe"): 1,
("Cafe", "Work"): 5, ("Park", "Work"): 8}
neighbours = {}
for (a, b), minutes in roads.items():
neighbours.setdefault(a, []).append((b, minutes))
print(neighbours["Home"])
[('Cafe', 4), ('Park', 2)]
从 Home 出发，你可以去 Cafe（4 分钟）或 Park（2 分钟）。
最直接的方法：列出每条路线
怎样才能最快从 Home 到 Work？最笨的办法是列出每条路线，再取其中最短的一条。
def all_routes(here, goal, route=None, total=0):
route = (route or []) + [here]
if here == goal:
yield route, total
return
for nxt, minutes in neighbours.get(here, []):
if nxt not in route:
yield from all_routes(nxt, goal, route, total + minutes)
for route, total in sorted(all_routes("Home", "Work"), key=lambda x: x[1]):
print(" -> ".join(route), total, "min")
Home -> Park -> Cafe -> Work 8 min
Home -> Cafe -> Work 9 min
Home -> Park -> Work 10 min
最快的路线经过 Park 和 Cafe，需要 8 分钟。看上去从 Home 直接到 Cafe 的路并不是最好，因为绕经 Park 会省一分钟。这就是最短路径问题。
这种笨办法在哪失效
数一数路线。只有 4 个地点的地图有 3 条路线。增加地点和道路后，路线数会相乘：如果每个地点都连接到另外 10 个地点，长度为 n 的路线大约有 10 × 10 × 10 ... 条，走 10 步时就是 10 billion 条，也就是一百亿条。把它们列出来毫无希望。真实的图有数百个节点。
第 6 和第 7 课的聪明算法不列出路线。它们为每个节点保留目前找到的最佳总和，并一步一步改进它。这就是全部思路，也是它们能保持快速的原因。
练习
- 运行代码。在另一个方向添加道路 ("Cafe", "Park"): 1。路线数量会改变吗？
- 添加一个 Gym 地点，加入 Home 到 Gym 为 3、Gym 到 Work 为 6 的道路。现在最快的路线是什么？
- 在纸上画出地图，凭直觉找出最快路线，再用代码核对。
下一篇：平均值和离散程度的辅助课（arbitrage-prereq-3-mean-stdev）。
