浙江大學-數據結構-選講旅遊規劃-8.3.2

dijkstra演算法呢，還有其它很多的各種變形的應用，

一種是當我們在求最短路徑的時候，我們還需要數等長的最短路徑一共有多少條，另外一類問題在所有的最短路裡面，我要找那個包含的邊數最少的最短路，先來看第一種，要數最短路徑有多少條，那麼很自然的，我們得加一個計數器的數組，我們把它叫作count,那對任意一個結點v,count[v]就記錄的是從源點到v的最短路徑一共有多少條，那初始化的時候呢，我們就是源點的這個count,要把它設為1，從源點的count等於1開始，我們開始執行dijkstra演算法，如果把一個v收到集合裡面，使得我們w可以找到一條更短的話，w的count應該怎麼樣更新呢？

其實因為從V到W就只有一條邊，所以從s到V,曾經有多少條最短路，那麼從s到W也就會有多少條最短路，你只要把這個數字繼承過來就可以了，那下一個問題是說，如果我找到了另外一條等長的最短路，這個時候W又要怎麼更新呢？

一個很常見的錯誤，當我們找到另一條等長路徑的時候，我們會讓這個count[W]就直接加1，我們以為是找到了另外1條等長路徑，但是且慢，你要停下來想一下，當我們這條新的等長路徑是從V走到W的時候，從s到V再到W,雖然從V到W只有一條邊，但是從s到V這邊的最短路可不一定是只有一條，所以V帶給W的，不一定是一條路，它可能是一堆等長最短路，那另外一個問題呢，我們要求邊數最少的最短路，其實仔細想一下，這個問題跟我們這個旅遊規劃其實是等價的，旅遊規劃問題要求的不是邊數最少，是邊數的費用和最少，但是如果你想想如果把費用全部定義為1，那不就等價為邊數最少嗎？所以這個問題，其實我們已經解決過了，但是在解決前面旅遊規劃問題的時候，我少說了一件事情，那就是費用的初始化怎麼做？那在這裡面呢，我不叫cost,我仍然把它叫做count,就是計數器來數這個邊數的，如果我數的是最短路徑有多少條，那我在原點的count初始化為1了，我要求的是邊數最少最短路的時候，那麼原點的這個count應該被初始化什麼呢？千萬不要把它初始化為1，一定要把它初始化為0，因為從s到s自己是沒有邊的，接下來的事情就很簡單了，我們前面其實也已經討論過了，如果我找到更短路的時候，這個count應該是什麼呢，應該是count[V]+1,那這個1你可以把它理解為一個邊的特殊的權重就是1，當這個邊有其它權重的時候，這個地方就應該是被換成其它的權重，如果我們找到了另外一條等長路的時候，這個處理方法其實也是一樣的。仍然是count[V]加上這條邊新的權重。