淺談最短路計數問題
本篇随筆淺談一下圖論中的最短路計數問題。
一、問題概念
最短路計數就是字面意思。我們可以找出一個圖的最短路，但是這張圖有多少條不同路徑都滿足這個路徑最短的限制呢？
這就是最短路計數問題。
二、問題解決
在我們正常跑最短路算法松弛的時候，再采用一個數組cnt來統計最短路的條數。
當然，我們要想辦法找出一個正确的松弛方案，也松弛cnt數組。
顯然地，如果有路徑可以松弛最短路，那麼這個計數就要重新計算，因為已經沒有用了。
是以此時
cnt[y]=cnt[x]
，是一個繼承。
還需要考慮什麼問題呢？
當目前路徑正好就是上一個節點的已知最短路時，這個計數就累加，合理性顯然。
是以
cnt[y]+=cnt[x]
。
是以我們就處理出了一個正确的cnt數組。
也就解決了這個問題。