Finding the k shortest paths, D Eppstein
這篇論文不錯。方法很好，但是我覺得讀的有點拗口。
說幾個重點nb的吧。
1. 能夠?qū)⒙窂接米疃搪窂綐浜?#8220;彎路”表示
2. 考慮到路徑的層次結(jié)構(gòu)。
如果考慮到以上兩點會有很多啟發(fā)的，之后還有幾個nb的：
3. 把堆表示在dag上。
4. 這個最最nb,很容易考慮到每次找到一個最小后綴，然后更新堆，但這樣復(fù)雜度就是nm的。而其通過將每個點的后綴重新組織成一個小堆。就控制住復(fù)雜度了！
這篇論文之前比賽的時候就很想看，后來搞輸入法的時候又聽說了，還是沒時間看。今天花了一下午看了還是挺開心的。不過覺得他有的地方方法有些冗余或者說不是很優(yōu)，什么時候再細(xì)細(xì)想想。今天好困。。。