課程「建立自己的套利機器人」的輔助課。第 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）。
