動機

就簡單地(口頭)描述演算法的重點在哪 話說這讓我想起許多做過的leetcode

手法

  • greedy
    • 選大(結果變大)
    • 去掉小(可能性變大)
      • 沒辦法就當前資訊知道結果
  • BFS
    • 走的node數最少
  • 列舉就是往組成的東西下手
    • 距離就會是 中點、起點

shortest-path

BFS

類別: BFS(走的node數最少)

從起點往外擴散，直到起點

每個點之間的距離都是一樣的，所以決定到終點之間距離多遠，是中間有多少點

def bfs(graph, start, end):
  vis = set()
  q = deque([(start,0)])
  while q:
    node, dis = q.popleft()
    if node is end:
      return dis
    else:
      vis.add(node)
      q.extend([(x, dis+1) for x in graph[node] if x not in vis])
  return -1 # cycle exists

Dijkstra

類別: BFS+greedy(能走過去的邊)

現在點之間的距離會變，所以需要一個表紀錄從起點到這個點的最短距離

會需要挑最短的下一個點，所以還要Heap去sort下一個最短的點

def dijkstra(graph, start, end):
  hq = [(0,start)] # heapq
  dists = defaultdict(lambda : float('inf')) # node -> distance
  dists[start] = 0
  while hq:
    dis, node = heappop(hq)

    for x,w in graph[node]:
      if dists[node]+w < dists[x]:
        dists[x] = dists[node]+w
        heappush(hq, (dists[x], x))
    
  return dists[end]

Floyd-Warshall

類別: 列舉(中間點)

試過每個中間點，在比原本距離小時更新，同時這可以知道所有點到另一個點的最短距離

def floyd-warshall(graph, start, end):
  dists = defaultdict(lambda : float('inf')) # node -> distance
  dists[(start,start)] = 0
  
  for mid in graph.keys():
    for a in graph.keys():
      for b in graph.keys(): 
        if dists[(a,b)] > dists[(a,mid)]+graph[mid][b]:
          dists[(a,b)] = dists[(a,mid)]+graph[mid][b]
  return dists[(start,end)]

Bellman–Ford

類別: 列舉(起點)

最長的長度就是所以點都走過一次(所以可以避免負環一直走的問題) 一直延長每個點的長度，最後就是最短路徑

def bellman–ford(graph, start, end):
  dists = defaultdict(lambda : float('inf')) # node -> distance
  dists[(start,start)] = 0
  
  for _ in len(graph.keys()):
    for a in graph.keys():
      for b,w in graph[a]: 
        if dists[b] > dists[a]+w:
          dists[b] = dists[a]+w
  if any(dists[b] > dists[a]+w for a in graph.keys() for b,w in graph[a]): # negtive cycle
    return None
  else:
    return dists[end]

Minimum Spanning Tree

Prim

類別: BFS+greedy(能走過去的邊)

Dijkstra是距離，dist[a]+graph[a][b] Prim，一樣是求最小，一樣點之間的距離會變，但SMT只要edge最小就好，所以用heap每次挑最小的edge

def prim(graph):
  start = next(graph.keys())
  hq = [(0,start)] # heapq
  dists = defaultdict(lambda : float('inf')) # node -> distance
  parent = {}
  dists[start] = 0
  parent[start] = None
  while hq:
    dis, node = heappop(hq)

    for x,w in graph[node]:
      if w < dists[x]: # HERE!!
        parent[x] = node
        dists[x] = w
        heappush(hq, (dists[x], x))
    
  return parent

Kruskal

類別: greedy(邊) 每次挑最小的edge去湊，直到變成一棵樹

def kruskal(graph):
  hq = []
  for a in graph.keys():
    for b,w in graph[a]:
      heappush(hq, (w, (a,b)))
  
  uf = {k:k for k in graph.keys()}
  ranks = {k:1 for k in graph.keys()}

  def find(a):
    while a != uf[a]:
      a = uf[a]
    return a

  def union(a,b):
    if find(a) != find(b):
      if ranks[a] >= ranks[b]:
        uf[b] = a
        rank[a] += rank[b]
      else:
        uf[a] = uf[b]
        rank[b] += rank[a]

  vis = set()
  while len(vis) < len(graph.keys()):
    _, (a,b) = heappop(hq)

    if a in vis and b in vis:
      continue
    else:
      [vis.add(x) for x in (a,b)]
      union(a,b)
  return uf

Flow Networks

這裡要求的是讓流過的水量最大

這個不像距離，每走一步就知道當前距離多少。 這要走到最後才會知道bottleneck在哪。

Ford-Fulkerson

類別: greedy(用到的edge最少, 所以算是BFS)

我們沒辦法就當前資訊知道結果如何，但可以在每次選擇中保留可能性

讓path用到的edge越少越好 (讓總edge的quota剩的多) 並且每次只丟掉最小的edge!!

所以用BFS讓走的node數最少，這樣就ok了

def BFS(graph, s, t):
    queue = deque()
    parent = {}

    queue.append(s)
    parent[s] = None

    while queue:
      a = queue.popleft()

      for b, val in enumerate(graph[a]):
          if b not in parent and val > 0: # 不走0，每次只丟掉最小的edge
              queue.append(b)
              parent[b] = a
          if b == t:
              return parent

    return False

def FordFulkerson(source, sink):
    max_flow = 0

    while (parent = BFS(graph, source, sink)) :
        path_flow = float("Inf")
        s = sink
        while s != source:
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]

        max_flow +=  path_flow

        v = sink
        while(v != source):
            u = parent[v]
            graph[u][v] -= path_flow # 不走0，每次只丟掉最小的edge
            graph[v][u] += path_flow # 反向流
            v = parent[v]

    return max_flow