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