資料結構與演算法(下)05 by 隨機客

非正題：今天上課算是比較輕鬆的一次(是進入狀況還是課比較好懂呢?我也不知道XD)，上課還被隨機客詢問(當然，我答不出來XD)，興起了換位子的念頭XD

---

2007/03/26 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Shortest-Path Tree Algorithm, 主要分有Bellman-Ford, Dijkstra Algorithm

在進入Algorithm前，先行討論此問題的背景

• The setting
  
  • The graph G = (V, E) is directed with edge length w. (此圖必需是個有權重的有向圖)
  • The length of each edge could be negative. (允許圖上的edge 為 negative)
  
  


• The problem
  
  • Input: A directed Graph G=(V, E) with weight edge w.
    A node r of G
  • Output: A tree T rooted at r such that the path of T from r to each node u of T is a shortest path from r to u in G.(yen3註：一個root 為r 的shortest path tree.)
  
  


• We may assume that each node in the graph is reachable from r.(yen3註：假設r 可以到達每個node)
  那麼在Graph中，有unreachable node，則一開始則remove掉，而不失一般性(Without loss of generality)，為什麼呢？
  尋找對r所有的unreachable node只需要花linear time，用DFS(depth First Search)從r開始，把所經過的點編號，而沒有被編號到的node就是unreachable node，而執行DFS只需要linear time，故此假設不失一般性


• Can a shortest path between node u and v contain a cycle? (是否會有cycle在shortest path tree上呢?)
  答案是否，我們把cycle weight sum分成三種狀況
  • cycle weight sum is positive: 此狀況不可能發生，因為這一定不是shortest path，因為一定不會通過，因為把此cycle 拿掉則path會更短
  • cycle weight sum is negative: u到v根本沒有shortest path，繞了n圈為最短，則繞了n+1圈會更短，則繞不完，所以有negative cycle weight的Graph, 則shortest path 不存在(這是一個if and only if)
  • cycle weight sum is 0: 則不會通過，就沒有cycle，這樣子可把cycle做一個remove的動作，使其cycle不在shortest path上


• Single-source shortest-path problem
  在此問題上為single path，但是與一般的path定義不同，一般的path定義為該node通過後則不能再通過，但是在此，我們比較確切關心edge weight sum


• Such a shortest-path tree always exists? 不一定，原因如上
  若r至任何一點u，都是reachable，就找所有可以走到的方法，事實上有可能是無限條，但是限制在G has no negative edge 和remove unreachable node 和 only think about single path ，則shortest path 則會變成有限條


• The shortest-path tree problem is equivalent to finding the distance from r to each node u in graph G. (尋找shortest distance和shortest path 是等價的問題)
  何謂等價的問題，若A和B是等價的問題，則找到A的答案之後，我們可以在linear time 找到B的答案，且找到B的答案之後，也可以在linear time 找到A的答案
  那麼為什麼shortest distance 和 shortest path是等價的問題？若已知shortest path，則把edge weight求其和即為distance，可在linear time 找到，若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到


• 補充說明：在演算法上所定義的linear time並不是指O(n)，而是指執行效率相對於input size，若input size 為O(n^2)，而RunTime也是O(n^2)，則我們說該演算法是linear time

終於可以描述演算法嘍XD

• Bellman-Ford Algorithm
  此演算法的方式如下
  
  • 設一個array d[u]為從r 到u的距離
  • 對其array做初始化的動作
    • Let d[u] = infinty for each node u of G
    • let d[r]=0(自己到自己距離為0)
  • Repeat improve對於d[u] for d(u)的估算
  
  而Relaxing edge(u,v)為

      If d[v] > d[u]+w(u,v) then
          let d[v] = d[u] + w(u,v)

  那何謂A phase of improvement

      For each edge(u, v) of G do
          relax edge(u, v)

  問題又來了，試問phase of improvement 要跑幾次才能確保答案的正確呢？
  如果node為n個，則跑n-1次就可確保答案正確性，每當我們跑了phase of improvement，則會有一點被改善(yen3註：竟然不會證Orz)
  那麼效率呢，由於有n個node，m個edge，每個點皆跑m個edge，所以Time Complexity = O(mn)
  
  第二個問題是，若圖中有negative cycle，則我們要怎麼得知？
  問題也很簡單，已知演算跑n-1次已經得解，若跑了第n個phase 而仍然有d[u]被改變的情形，則知道與原先預想的不合，此圖有negative cycle
  為什麼？在s.31說明(yen3註：證明竟然忘了...真神Orz)
  
  若該Graph 為一個 Directed Acyclic Graph DAG呢? 方法如下
  

  • 先對該DAG做topological sort
  • 根據topological sort 的順序，由小到大(slight 上寫由for 1 to n)做relaxing動作

  其Running Time 是 O(m+n)


• Dijkstra Algorithm
  
  (題外話：Edsger W. Dijkstra 是提出“Goto is considered harmful.”的人)(yen3註：此話真的是powerful，對於現在學assembly language的我而言更是一個有趣的問題。)
  
  此演算法是一個極具powerful的演算法，此演算法求shortest path是建立在無non-negative weight edge, non-negative-cycle的DAG上，方法如下(此方法不用依靠topological sort做前置作業)
  

  • 做與Bellman-Ford Algorithm同樣的初始化動作(與對其array做初始化的動作相同)
  • 每一個iteration中，尋找unprocessed node中，尋找到目前為止smallest path做relaxing，直到每一點都做完為止(換句話說，在所有未處理的點找到該點花費最少的來做處理)

  
  此方法的正確性呢?由s.50得知。假設u是unprocessed minimal node，而在處理到u node時出錯了，而y node 與processed node 的範圍只用一條edge連結，所以我們確信d[y] = d(y)，但是我們又說u是unprocessed minimal node，而用y連過去則會讓d[u] > d(u) >=d(y) = d[y] 矛盾(yen3註：證的真爛Orz)
  
  則Running Time用 Naïve implementation: O(n2 + m).
  With Fibonacci heap: O(n log n + m).

---

---
聽Josh Ko說明才得知簡報上的數學式是用TeX4PPT做的，來找找做個介紹