在了解了1-最短路徑的計算方式后，我們看看N-最短路徑的計算。
N-最短路徑的計算方式與1-最短路徑基本相同，只是在記錄所有可達路徑時，要保留最短的前N個結(jié)果。讓我們?nèi)匀灰陨掀恼碌陌咐齺砜纯慈绾螌崿F(xiàn)N-最短路徑的運算。
1、數(shù)據(jù)表示
這里我們?nèi)匀谎赜们拔睦樱瑢ο聢D求N-最短路徑，每條邊的權(quán)重已經(jīng)在圖中標(biāo)注出來了。
（圖一）
2、運算過程
仍然象1-最短路徑一樣，計算出每個結(jié)點上可達N-最短路的PreNode。我們這里以2-最短路徑為例：
1）首先計算出每個結(jié)點上所有可達路徑的可能路徑長度并按從小到大排序。
2）根據(jù)排序結(jié)果取前2種路徑長度并分別記錄進各結(jié)點的PreNode隊列。如下圖：
（圖二）
在該圖中，到達1號、2號、3號結(jié)點的路徑雖然有多條，但長度只有一種長度，但到達4號“D”結(jié)點的路徑長度有兩種，即長度可能是3也可能是4，此時在“最短路”處（index＝0）記錄長度為3時的PreNode，在“次短路”處（index＝1）處記錄長度為4時的PreNode，依此類推。
值得注意的是，此時用來記錄PreNode的坐標(biāo)已經(jīng)由前文求“1-最短路徑”時的一個數(shù)（ParentNode值)變?yōu)?個數(shù)（ParentNode值以及index值）。
如圖二所示，到達6號“末”結(jié)點的次短路徑由兩個ParentNode，一個是index=0中的4號結(jié)點，一個是index=1的5號結(jié)點，它們都使得總路徑長度為6。
3、具體實現(xiàn)
在具體實現(xiàn)上述算法時，首先要求得所有可能路徑的長度，這在SharpICTCLAS中是通過一個EnQueueCurNodeEdges方法實現(xiàn)的，上篇文章給出了它的簡化版本的代碼，這里將完整的求N-最短路徑的EnQueueCurNodeEdges方法代碼放上來：
//====================================================================
// 將所有到當(dāng)前結(jié)點（nCurNode）可能的邊根據(jù)eWeight排序并壓入隊列
//====================================================================
private static void EnQueueCurNodeEdges(ref CQueue queWork, int nCurNode)
{
int nPreNode;
double eWeight;
ChainItem<ChainContent> pEdgeList;
queWork.Clear();
pEdgeList = m_apCost.GetFirstElementOfCol(nCurNode);
// Get all the edges
while (pEdgeList != null && pEdgeList.col == nCurNode)
{
nPreNode = pEdgeList.row; // 很特別的命令，利用了row與col的關(guān)系
eWeight = pEdgeList.Content.eWeight; //Get the eWeight of edges
for (int i = 0; i < m_nValueKind; i++)
{
// 第一個結(jié)點，沒有PreNode，直接加入隊列
if (nPreNode == 0)
{
queWork.EnQueue(new QueueElement(nPreNode, i, eWeight));
break;
}
// 如果PreNode的Weight == Predefine.INFINITE_VALUE，則沒有必要繼續(xù)下去了
if (m_pWeight[nPreNode - 1][i] == Predefine.INFINITE_VALUE)
break;
queWork.EnQueue(new QueueElement(nPreNode, i, eWeight + m_pWeight[nPreNode - 1][i]));
}
pEdgeList = pEdgeList.next;
}
}
這里的m_nValueKind就是你希望N-最短路徑保留幾種路徑的結(jié)果。
當(dāng)m_nValueKind＝2時，我們求得了2-最短路徑，路徑長度有兩種，分別長度為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,
4、求解N-最短路徑
N-最短路徑的最終輸出與上篇文章完全一致，仍然是借助堆棧完成的。只不過根據(jù)index的取值的不同，分多次完成壓棧與出棧的操作而已。此處就不再重復(fù)，感興趣的可以再看看上一篇文章。
1）N-最短路徑中用來記錄PreNode的坐標(biāo)由前文求“1-最短路徑”時的一個數(shù)（ParentNode值)變?yōu)?個數(shù)（ParentNode值以及index值）。
2）N-最短路徑并不意味著求得得路徑只有N條。
3）文中只演示了2-最短路徑，但可以推廣到N-最短路徑。程序求得的3-最短路徑中，最長的路徑為：（0, 1, 3, 4, 6）與（0, 1, 2, 3, 4, 6），它們的長度都是7。
來源：http://www.cnblogs.com/zhenyulu/category/85598.html