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

03-06

旅遊規劃

旅遊規劃這道題看上去還是比較直白的，一看我們就知道這是一個圖論的問題，一看就知道這是一個單元最短路徑的問題，一看就知道是可以用dijkstra演算法來解決的問題，但是如果你直接把dijkstra演算法複製粘貼上去，你能真的解決這個問題嗎？稍微還有一點點複雜，因為它多了一點條件，

麻煩的地方在於每一條邊的權重，在這道題裡面，我們不止一種權重，第一種權重呢，是我們都想的到的，標準的權重是距離，另外還有一種權重，它指的是收費，那我們這個題目要求的首先我是以距離為標準來判斷最短路的，我要找一個距離意義上的最短路徑，當這樣的路徑不止一條的時候，那這個時候我就要找權重2最小的，也就是收費最便宜的那條路徑，這個是我們的樣例輸入，

那麼對應的構造出的一副圖就長的是這個樣子

我們以0為起點，3為終點，綠色代表距離這個權重，紫色代表的是收費這個權重，如果我們只想找一條最便宜的路徑，那我們直接從0走到3就對了，這條路上只需要花10塊錢，但是不行，因為這條路太遠了，它的距離是4，你別看我在這畫的這麼短，說不定人家是翻了一個山頭呢，因為它要翻一個山頭，所以沒人願意走這條路，所以這條路的收費便宜，但是我們這道題目裡頭，首先要求距離最短，所以這條路是不能用的，最短距離的路徑在這裡頭我們有兩條，一個從0到1到3，在一個從0到2到3，這兩條路徑的距離都是等於3，一個是1加2，一個是2加1，在距離並列的情況下，我們才去比較它們的收費，左邊路徑收費50，右邊收費40，最後我們輸出選擇應該選擇的是0->2->3這條路徑，解決問題的方法，肯定還是要用dijkstra演算法，或者說是基於dijkstra演算法的，它仍然是一個單源最短路的問題，dijkstra演算法是一個結點一個結點往集合裡面去收集的，每當收集進來一個結點的時候，它要檢查一下，其它結點距離有沒有被影響，會得到一個更短的距離，如果更短的話，我來刷新這個距離，如果是等長的話，我就什麼都不做了，那關鍵的區別就在這裡，當距離相等的時候不能什麼都不做，我還需要按照收費來做一個更新，

具體要怎麼更新呢，我們接下去來看核心的演算法，首先我們來回憶一下經典的dijkstra演算法長什麼樣，

這個就是dijkstra演算法直接copy過來的，我們先給了一個源點s,然後進入while循環，每次從這個dist裡面最小的挑一個沒有收錄的(V = 未收錄頂點中dist最小者)，然後標記一下把它收進來（collected[V] = true)，再檢查它的每一個鄰接點(for (V的每個鄰接點W))，如果這個鄰接點還沒有被收錄(if (collected[W] == false)), 並且由於V點的加入，使我們得到了一個更短的W距離, 那麼我們更新這個距離(dist[W] = dist[V] + E<v,w>),同時更新它的最短路徑(path[W] = V),這就是最簡單的dijkstra演算法，那在我們旅遊規劃的問題裡面，當我們需要更新路徑的時候，我們必須同時還要更新什麼？我們還要更新另外一個權重，

我們為另外一個權重可以建另外一個數組，叫做cost,cost[W]裡面存的就是從s走到W當前這個路徑上所有費用的和，當我們找到一條最短路的時候，因為路徑被更新了，所以費用也需要被更新，它要被更新為什麼呢，就是從s走到V的所有的費用，加上從v走到w，這條邊的費用，這個是很好理解的(cost[W] = cost[V] + C<v,w>),除了dijkstra演算法的原始演算法之外，我們還需要加一條判斷就是如果距離如果不是更短，但是它是相等的時候，所以這裡要加一個else if

當我們找到了另外一條等長的最短路徑並且這條路徑上新的費用比原來的費用要更小的話，那麼我們也要更新路徑，我們首先要更新它的費用，同時別忘了更新一下這個path,