什么問題是最短路問題
對(duì)路徑的合理選取使得這條路徑上的權(quán)重最后的結(jié)果符合題目要求的問題，一般都能夠通過最短路算法解決，在這樣的一個(gè)大前提上，對(duì)于權(quán)值和路徑的要求不同，可以使得問題發(fā)生不同的變種，根據(jù)是實(shí)際情況，采取不同的方法予以解決
對(duì)于特定問題的特定分析
對(duì)于最短路問題的變形大致有以下的幾種可能
- 求解路徑中是否存在負(fù)環(huán)類問題
- 有向圖中的往返最短問題
- APSP問題
- 最單純的最短路問題
- 最短路中的最長(zhǎng)路問題
求解路徑中是否存在負(fù)環(huán)類問題，對(duì)于一個(gè)問題，因?yàn)樗麄兊臋?quán)值使得出現(xiàn)一個(gè)能夠?qū)τ谠诃h(huán)上的點(diǎn)的路徑的距離不斷改變是這一類題目的特征，也就是說，無論是匯率，時(shí)間，只要是通過求解所存在的路上出現(xiàn)了對(duì)于某幾個(gè)點(diǎn)的距離一直處于刷新狀態(tài)，永遠(yuǎn)無法確定下來，就可以確定是一個(gè)求負(fù)環(huán)問題。
對(duì)于求負(fù)環(huán)問題一般來說使用的是SPFA算法，對(duì)于負(fù)環(huán)問題，SPFA算法原理中本來就容許有負(fù)環(huán)存在，當(dāng)一條路徑的變換距離的操作已經(jīng)超過了算法的容許度，按照定義，就可以知道其這樣一條路中出現(xiàn)了負(fù)環(huán)回路。有向圖中的往返最短問題，這樣的問題主要是有一個(gè)單源起點(diǎn)，然后題目一般通過各種方式詢問它到某一個(gè)點(diǎn)的到和回來的問題，因?yàn)樗怯邢驁D，實(shí)際上也就解決了你到一個(gè)點(diǎn)而且回來的最短距離且邊不重復(fù)使用的問題，這樣的問題其實(shí)可以直接按照題意輸入一次有向圖，然后把原有向圖的方向倒轉(zhuǎn)，重新輸入一次，這樣子的話，實(shí)際上就是把回來的路變換方向變成再一次出去的路，重新轉(zhuǎn)化成SPSP問題，這樣的話根據(jù)圖的稠密程度就可以使用dijkstra或者SPFA算法求解
APSP問題，由于現(xiàn)在所接觸到的最短路算法只有少數(shù)的幾個(gè)，所以不是很清楚是否還有更優(yōu)的解法，實(shí)際上現(xiàn)在觀念中的對(duì)于APSP問題來說似乎是floyd算法比較有利，因?yàn)榻?jīng)過預(yù)處理之后就已經(jīng)對(duì)所有的點(diǎn)的距離獲得一個(gè)求解，所以查詢的時(shí)候只會(huì)消耗O(1)的時(shí)間復(fù)雜度。但是近來似乎接觸到了一種優(yōu)化版的SPFA，在求解APSP問題的時(shí)候比floyd算法在比較短的時(shí)間內(nèi)能夠結(jié)局，因?yàn)閷?duì)于floyd算法，所有最短路的距離是必須全部求解的，但是對(duì)于一些比較水一點(diǎn)的數(shù)據(jù)，其實(shí)它的查詢是不一定能夠達(dá)到APSP問題，所以我認(rèn)為其實(shí)無論是在實(shí)際應(yīng)用還是比賽中改良版的SPFA似乎都應(yīng)該有更好的效率
最單純的最短路問題的解決只需要注意到的是圖是否是稠密圖，然后針對(duì)其使用最短路算法就可以了，另外要插一句嘴，其實(shí)所謂的并行最短路問題也是最單純的最短路問題（想一想為啥）
最短路的最長(zhǎng)路問題，這個(gè)我只用過floyd和dijkstra算法解決，但是比較通用的算法應(yīng)該是dijkstra算法，在經(jīng)過最小heap優(yōu)化之后，dijkstra算法對(duì)于更多的最短路存在一個(gè)適配性，雖然個(gè)人比較習(xí)慣的是SPFA就是了。對(duì)于貪心的過程進(jìn)行一個(gè)中轉(zhuǎn)量的使用就可以獲得這個(gè)問題的解。
這個(gè)星期主要是重新理通了一遍所熟識(shí)的最短路算法的求解和原理，題目的難度實(shí)在是不高，可能是因?yàn)閗uangbin并沒找到這個(gè)專題的更難得變種，切起來比較簡(jiǎn)單，比較需要注意的是，因?yàn)橐恍┧饺说氖虑樗詻_勁減少，不是很應(yīng)該。對(duì)于算法的改良和證明講解暫時(shí)不做說明，主要是因?yàn)楸容^繁瑣。SPFA算法需要考慮和魔改的地方我也發(fā)到群里面去了。
在樹上看到對(duì)于最短路問題似乎是有差分約束的拓展，這兩天我找個(gè)時(shí)間了解一下，希望諸君效率也有一個(gè)提升，多少對(duì)得住自己便是了
鯽魚
2017-3-28
