N-最短路徑 是中科院分詞工具NLPIR進(jìn)行分詞用到的一個(gè)重要算法，張華平、劉群老師在論文《基于N-最短路徑方法的中文詞語(yǔ)粗分模型》中做了比較詳細(xì)的介紹。該算法算法基本思想很簡(jiǎn)單，就是給定一待處理字串，根據(jù)詞典，找出詞典中所有可能的詞，構(gòu)造出字串的一個(gè)有向無(wú)環(huán)圖，算出從開(kāi)始到結(jié)束所有路徑中最短的前N條路徑。因?yàn)樵试S相等長(zhǎng)度的路徑并列，故最終的結(jié)果集合會(huì)大于或等于N。

根據(jù)算法思想，當(dāng)我們拿到一個(gè)字串后，首先構(gòu)造圖，接著針對(duì)圖計(jì)算最短路徑。下面以一個(gè)例子“他說(shuō)的確實(shí)在理”進(jìn)行說(shuō)明，開(kāi)始為了能夠簡(jiǎn)單說(shuō)明，首先假設(shè)圖上的邊權(quán)值均為1。?

先給出對(duì)這句話的3-最短路(即路徑最短的前3名, 因?yàn)橛胁⒘谐煞? 所以可能候選路徑大于3)徑求解過(guò)程圖：?

從節(jié)點(diǎn)4開(kāi)始, 因?yàn)?是第一個(gè)出現(xiàn)多個(gè)前驅(qū)節(jié)點(diǎn)的

?

首先看圖中上方，它是根據(jù)一個(gè)已有詞典構(gòu)造出的有向無(wú)環(huán)圖。它將字串分為單個(gè)的字，每個(gè)字用圖中相鄰的兩個(gè)結(jié)點(diǎn)表示，故對(duì)于長(zhǎng)度為n的字串，需要n+1個(gè)結(jié)點(diǎn)。兩節(jié)點(diǎn)間若有邊，則表示兩節(jié)點(diǎn)間所包含的所有結(jié)點(diǎn)構(gòu)成的詞，如圖中結(jié)點(diǎn)2、3、4構(gòu)成詞“的確”。

圖構(gòu)造出來(lái)后，接下來(lái)就要計(jì)算最短路徑，N-最短路徑是基于Dijkstra算法的一種簡(jiǎn)單擴(kuò)展，它在每個(gè)結(jié)點(diǎn)處記錄了N個(gè)最短路徑值與該結(jié)點(diǎn)的前驅(qū)，具體過(guò)程如上圖中下方列表。Table(4)表示位于結(jié)點(diǎn)4時(shí)的最短路徑情況，表示從結(jié)點(diǎn)0到4有兩條路徑，長(zhǎng)度為3的路徑前驅(qū)為2；長(zhǎng)度為4的路徑前驅(qū)為3。前驅(qū)括號(hào)里面第二個(gè)數(shù)表示對(duì)相同前驅(qū)結(jié)點(diǎn)的區(qū)分，如（4,1）、（4,2）。由列表可知，該字串的3-最短路徑結(jié)果集合為｛5,5,6,6,7｝。

當(dāng)然，在實(shí)際情況中，權(quán)值不可能都設(shè)為1的，否則隨著字串長(zhǎng)度n和最短路徑N的增大，長(zhǎng)度相同的路徑數(shù)將會(huì)急劇增加。為了解決這樣的問(wèn)題，我們需要通過(guò)某種策略為有向圖的邊賦權(quán)重，很自然的想法就是邊的權(quán)重就是該詞出現(xiàn)的可能性。

NShortPath的基本思想是Dijkstra算法的變種，拿1-最短路來(lái)說(shuō)吧，先Dijkstra求一次最短路，然后沿著最短路的路徑走下去，只不過(guò)在走到某個(gè)節(jié)點(diǎn)的時(shí)候，檢查到該節(jié)點(diǎn)在路徑上的下一個(gè)節(jié)點(diǎn)是否還有別的路到它（從PreNode查），如果有，就走這些別的路中的沒(méi)走過(guò)第一條（它們都是最短路上的途徑節(jié)點(diǎn)）。然后推廣到N-最短路，N-最短路中PreNode有N個(gè)，分別對(duì)應(yīng)n-最短路時(shí)候的PreNode，就這么簡(jiǎn)單。

圖解

再談PreNode的準(zhǔn)備

需要為每個(gè)頂點(diǎn)維護(hù)一個(gè)最小堆，最小堆里儲(chǔ)存的是邊的花費(fèi)，每條邊的終點(diǎn)是這個(gè)頂點(diǎn)。還需要維護(hù)到每個(gè)頂點(diǎn)的前N個(gè)最小路徑的花費(fèi)：

回憶一下Dijkstra求最短路的時(shí)候，我們只需記錄一個(gè)最短路的累計(jì)花費(fèi)就行了

這與此處的N-最短路徑顯著不同。

在遍歷圖的時(shí)候，與Dijkstra最短路徑不同，N-最短路徑從第二個(gè)節(jié)點(diǎn)開(kāi)始，需要將當(dāng)前節(jié)點(diǎn)可能到達(dá)的邊根據(jù)累積第i短長(zhǎng)度+該邊的長(zhǎng)度之和排序記錄到PreNode隊(duì)列數(shù)組中，排序由CQueue完成的。

然后從CQueue出隊(duì)，這樣路徑長(zhǎng)度就是升序了，按順序更新 weightArray[當(dāng)前節(jié)點(diǎn)][第幾短路]就行了。

另外CQueue是一個(gè)不同于普通隊(duì)列的隊(duì)列，它維護(hù)了一個(gè)當(dāng)前指針（下圖的藍(lán)色部分），這個(gè)藍(lán)色指針在求解第i短路徑的時(shí)候會(huì)用到。

假定看到這里，算法已經(jīng)計(jì)算出了正確的PreNode隊(duì)列，下面討論如何從PreNode中找出N最短路徑的確切途經(jīng)節(jié)點(diǎn)集合。

1-最短路徑的求解

整個(gè)計(jì)算過(guò)程維護(hù)了一個(gè)路徑棧，對(duì)于上圖來(lái)說(shuō)，

1）首先將最后一個(gè)元素壓入棧（本例中是6號(hào)結(jié)點(diǎn)），什么時(shí)候這個(gè)元素彈出棧，什么時(shí)候整個(gè)任務(wù)結(jié)束。

2）對(duì)于每個(gè)結(jié)點(diǎn)的PreNode隊(duì)列，維護(hù)了一個(gè)當(dāng)前指針，初始狀態(tài)都指向PreNode隊(duì)列中第一個(gè)元素。這個(gè)指針是由CQueue維護(hù)的，嚴(yán)格來(lái)講不屬于算法關(guān)心的問(wèn)題。

3）從右向左依次取出PreNode隊(duì)列中的當(dāng)前元素（當(dāng)前元素出隊(duì)）并壓入棧，并將隊(duì)列指針重新指向隊(duì)列中第一個(gè)元素。如上圖：6號(hào)元素PreNode是3，3號(hào)元素PreNode是1，1號(hào)元素PreNode是0。

4）當(dāng)?shù)谝粋€(gè)元素壓入棧后，輸出棧內(nèi)容即為一條隊(duì)列。本例中0, 1, 3, 6便是一條最短路徑。

5）將棧中的內(nèi)容依次彈出，每彈出一個(gè)元素，就將當(dāng)時(shí)壓棧時(shí)該元素對(duì)應(yīng)的PreNode隊(duì)列指針下移一格。如果到了末尾無(wú)法下移，則繼續(xù)執(zhí)行第5步（也就是繼續(xù)出棧），如果仍然可以移動(dòng)，則執(zhí)行第3步。

對(duì)于本例，先將“0”彈出棧，在路徑上0的下一個(gè)是1，得出該元素對(duì)應(yīng)的是1號(hào)“A”結(jié)點(diǎn)的PreNode隊(duì)列，該隊(duì)列的當(dāng)前指針已經(jīng)無(wú)法下移，因此繼續(xù)彈出棧中的“1” ；同理該元素對(duì)應(yīng)3號(hào)“C”結(jié)點(diǎn)，因此將3號(hào)“C”結(jié)點(diǎn)對(duì)應(yīng)的PreNode隊(duì)列指針下移。由于可以移動(dòng)，因此將隊(duì)列中的2壓入隊(duì)列，2號(hào)“B”結(jié)點(diǎn)的PreNode是1，因此再壓入1，依次類(lèi)推，直到0被壓入，此時(shí)又得到了一條最短路徑，那就是0，1，2，3，6。如下圖：

再往下，0、1、2都被彈出棧，3被彈出棧后，由于它對(duì)應(yīng)的6號(hào)元素PreNode隊(duì)列記錄指針仍然可以下移，因此將5壓入堆棧并依次將其PreNode入棧，直到0被入棧。此時(shí)輸出第3條最短路徑：0, 1, 2, 4, 5, 6。如下圖：

輸出完成后，緊接著又是出棧，此時(shí)已經(jīng)沒(méi)有任何棧元素對(duì)應(yīng)的PreNode隊(duì)列指針可以下移，于是堆棧中的最后一個(gè)元素6也被彈出棧，此時(shí)輸出工作完全結(jié)束。我們得到了3條最短路徑，分別是：

0, 1, 3, 6,

0, 1, 2, 3, 6,

0, 1, 2, 4, 5, 6,

推廣到N-最短路

N-最短路中PreNode有N個(gè)，分別對(duì)應(yīng)n-最短路時(shí)候的PreNode，也就是當(dāng)前路徑是第n短的時(shí)候，當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的PreNode隊(duì)列。

在該圖中，觀察黃顏色的路徑長(zhǎng)度表格，到達(dá)1號(hào)、2號(hào)、3號(hào)結(jié)點(diǎn)的路徑雖然有多條，但長(zhǎng)度只有一種長(zhǎng)度，但到達(dá)4號(hào)“D”結(jié)點(diǎn)的路徑長(zhǎng)度有兩種，即長(zhǎng)度可能是3也可能是4，此時(shí)在“最短路”處（index＝0）記錄長(zhǎng)度為3時(shí)的PreNode，在“次短路”處（index＝1）處記錄長(zhǎng)度為4時(shí)的PreNode，依此類(lèi)推。

值得注意的是，此時(shí)用來(lái)記錄PreNode的坐標(biāo)已經(jīng)由前文求“1-最短路徑”時(shí)的一個(gè)數(shù)（ParentNode值)變?yōu)?個(gè)數(shù)（ParentNode值以及index值）。

如上圖所示，到達(dá)6號(hào)“末”結(jié)點(diǎn)的次短路徑有兩個(gè)ParentNode，一個(gè)是index=0中的4號(hào)結(jié)點(diǎn)，一個(gè)是index=1的5號(hào)結(jié)點(diǎn)，它們都使得總路徑長(zhǎng)度為6。

當(dāng)N=2時(shí)，我們求得了2-最短路徑，路徑長(zhǎng)度有兩種，分別長(zhǎng)度為5和6，而路徑總共有6條，如下：

最短路徑：

0, 1, 3, 6,

0, 1, 2, 3, 6,

0, 1, 2, 4, 5, 6,

========================

次短路徑

0, 1, 2, 4, 6,

0, 1, 3, 4, 5, 6,

0, 1, 2, 3, 4, 5, 6,

---------------------?

文章來(lái)源于random-walk的博客