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

非正題：這一次是有史以來上課最緊張的一天(雖然課程內容不怎麼緊張)，Josh 身體不適，嗯，有點緊張，但上課越來越進入狀況，只是對沒學過圖論的我還是一個很大的問題，早上六點起來騎車也是一個不錯的經驗，只是一直下雨XD

---

2007/04/02 資料結構與演算法(下) 06 呂學一 投影片

今天的主題為算出all-pairs shorest paths tree(yen3註：相當於把Graph上所有的node都建shortest path tree)，而今日的主題有三，Naïve algorithms和改善其效率的dynamic programming和Reweighting(yen3註：若能把edge weight 都變正，則可用Dijkstra's Algorithm)。在進入正題之前，先討論。

• The setting
  對於問題的setting仍與上禮拜相同，有一Graph G=(V, E)，而每個edge有weight，而edge weight允許為negative
  


• The Problem
  
  • Input: Edge weight matrix w, where w(i, j) stands for the length of edge (i, j).
  • Output:The distance matrix d, where d(i, j) stands for the length of a shortest path from node i to node j.
  
  今天的問題仍然在討論shortest path trees和distance是否等價
  • 從all-pair shortest path tree求得distance table
    這相當的直覺，有n個node，而每一次皆跑n-1個node，總次數為n*(n-1)，所以為O(N^2)
  • 從distance table 算出 all-pair shotest path trees
    這看起來不怎麼直覺，但是就上禮拜的從distance找回shortest path tree的方法，是一樣的

    若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到

    而每個row至多把所有edge走完為m次，而有n個node，所以為O(nm)(yen3註：懶的寫XD)
  
  所以今天重點仍舊是在shortest distance上
  

• Naïve algorithm - all-pairs distance
  根據上禮拜所教的演算法(Bellman-Ford, Lawler, Dijkstra)，Naïve algorithm - general edge weight上(可以有negative edge, negative cycle)，方法如下。
  
  • 先Run Bellman-Ford 確定G中有沒有negative cycle，如果有negative cycle則停止，可在O(mn)時間內完成(yen3註：怪怪的，因為只跑一次真的能保證能找到negative cycle?)
  • for each node in Graph G Run Bellman-Ford Algorithm，每一個點都是O(mn)，所以Time complexity 為 O(mn^2)，最多是任意兩點都有edge，則為C(n,2)*O(mn^2) 則worest case 為O(mn^4)
  
  若確定為each edge weight is nonegative edge weight則可使用Dijkstra Algorithm，for each node in Graph G run Dijkstra Algorithm，由於是nonegative edge weight，所以不用擔心negative cycle，每一個node為O(m+n^2)，所以為O(mn+n^3)，而使用Fibonacci heap的話，Time complexity 為O(mn+ n^2 log n)

那麼今天真正的主題就是，要把Naïve algorithm speeding up(yen3註：上禮拜是一個怪好笑的舌頭，這禮拜為一個戰鬥機代表speeding up XD)


• Dynamic Programming
  (JK註：以下的DP皆建立在Graph無negative cycle 上)(一種聰明的填表法，想辦法讓走過的都留下痕跡，recursive definition很重要)，首先，建立一個matrix w(i,j)，而w_k(i,j)指的是所有i to j 的path中，所使用的edges <= k中，挑選min edge weight sum為其value，定義如下
  
  • w_1(i, j) = w(i,j)
  • w_{n-1}(i, j) = d(i, j)
  
  而Recurrence Relation為
  • w_1 = w(i,j)
  • w_{2k}(i, j)= \min_{1<=t<=n}(w_k(i,t)+w_k(t,j))
  
  算出一個的(i,j)為O(n^2)*O(n)，而我們可用O(log n) 求完所有的點，所以總花費時間為O(n^3 log n)



• Dynamic Programming - Floyd-Warshall algorithm
  定義一個matrix, 而d_k(i,j)的定義為，把每個node編號，而從i到j的中繼點編號不能超過k，所以對於每個d_k(i,j)我們都有如下定義
  • d_0(i,j) = w(i,j) (it's clear)
  • d_n(i,j) = d(i,j) (d_n 是所有的點都可以經過或不經過，所以path distance就是shortest path)
  
  而它的 Recurrence Relation如下
  • d_0(i,j) = w(i,j)
  • d_{k+1}(i,j) = min{d_k(i,j), d_k(i,k+1) + d_k(k+1, j)} (把整個路徑分成i to k, k+1 to j而分別求)(yen3註：寫到這邊有一點後繼無力的感覺XD)


• Reweighting
  用意是把有negative weight edge 變成正的，如此一來可使用Dijkstra's Algorithm 做一個speeding up的動作。但是方法不是直接對每一個edge weight 加上一個constant value，這樣子會造成shortest path 改變(例如說，本來繞了很多圈在經過negative weight edge，可能因為加了一個constant value而造成不經過。)，在此，Johnson提出了一個方法
  • Assign a weight h(i) to each node i in G.(給每個node一個weight)
  • for any path P from node i to node j, we have
    \hat{w}(P) = w(P) + h(i) - h(j)
    (New edge weight = old edge weight + 起點的 node weight – 終點的 node weight)(前一個edge 的 end node weight會和下一start node weight做抵消動作，故不影響shortest path，而知道shortest path 之後，利用原圖G，即可在O(n^2)求出原圖的distance)
    
  • 此方法成立嗎？假設戴帽子的P為最短的，而沒有戴帽子P卻不是最短的，那麼，我們必然能找到一個Q比沒有戴帽子的P還要短，然後根據reweighting的方法，我們得到帶帽子的Q竟然比帶帽子的P還要來的短，矛盾，故沒有帶帽子的P一定是shortest path
  
  問題又來了，這樣子做reweighting的動作，並不保證edge weight為nonegative，所以Johnson提出的方法如下
  • 多設立一個為0的node，使其node連接到每一個node上，而edge weight 為 0
  • 如果G沒有negative cycle，則戴帽子的G也不會有negatvie cycle
  • 對於每個node的h(i)設為0 至每一個node 的weight sum
    可利用s.29的圖來說明，用三角不等式即可得證，d(0,j) <= d(0,i) + d(i, j)，d(0, j) 為shortest path，則d(0,i) + d(i, j) 至多有可能為d(0,j) 的其中一個解。
  
  使用了Johnson's Reweighting的方法之後由於edge weight為nonegative，所以可使用Dijkstra's algorithm，running time可達到O(mn+n^2 log n)

---

---
下次寫作時間不要拖那麼長了..Orz