Finding the k shortest paths, D Eppstein

這篇論文不錯。方法很好，但是我覺得讀的有點拗口。
說幾個重點nb的吧。
1. 能夠將路徑用最短路徑樹和“彎路”表示
2. 考慮到路徑的層次結構。
如果考慮到以上兩點會有很多啟發的，之后還有幾個nb的：
3. 把堆表示在dag上。
4. 這個最最nb,很容易考慮到每次找到一個最小后綴，然后更新堆，但這樣復雜度就是nm的。而其通過將每個點的后綴重新組織成一個小堆。就控制住復雜度了！

這篇論文之前比賽的時候就很想看，后來搞輸入法的時候又聽說了，還是沒時間看。今天花了一下午看了還是挺開心的。不過覺得他有的地方方法有些冗余或者說不是很優，什么時候再細細想想。今天好困。。。