浙江大學-數據結構-小白專場：最小路徑問題-7.1.1

最短路徑問題

上次我們講到007從一個孤島上給你發了一個求救信號，當時你只能給他回一個yes或者是no,如果是no,那也就算了，他也就絕望了，但是如果他真的可以活命的話，你只給他回一個yes,是不是太不負責了？你要真的想救他的話，你不僅僅是要告訴他一個yes,你應該告訴他，怎麼樣跳，才能跳到岸上去，當然你給他的路徑應該是最短路徑，這也就是我們圖論裡面的最短路問題，我們現實生活中還有很多問題都可以歸結為最短路徑的問題，比如說地鐵圖，

針對這幅圖有好幾種問題的問法，比如說，我給了你兩個站點的名字，一個A，一個B，那我要問你從A到B的最短路是哪一條，當然這個就是一個非常直接的問法，在這個問題里，我們對應的圖的頂點就是一個一個的站點，那麼我們所謂的路徑，就是兩個站點之間有直通的路線，那我們就說它們之間有一條邊，那所謂的最短路徑呢，指的是最短距離，所以呢，邊上面的權重對應的就是兩個站點之間的距離，所以我們要找的就是從A站點到B站點它的所有可達路徑中間距離的和最短的那一條，這就是最短路徑，另外一種問法還可以是這樣的，我要找從A站點到B站點最便宜的那條路，這個時候其實也是一個最短路的問題，這個時候什麼叫長，什麼叫短呢？那其實區別就在於邊上面的權重你賦予它什麼意義，如果我要找最便宜的路徑，兩點之間邊的權重就應該定義成票的價格，所以我們要找的就是整個票的價格的和，是最小的那條路，還有一種問法，就是說我要找A站點到B站點最快的路徑，如果我是這樣定義快的，A站點到B站點中間經停的站點最少，這樣我就認為它最快，那麼這個問題我們應該怎麼抽象呢？實際上這個問題就相當於是我要數中間的經停站，其實經停站的個數跟它的邊的條數是有對應關係的，我要找最少的經停站，也就是要數中間經過最少多少條邊，那麼在這個問題裡頭，那個邊的權重就無所謂了，我們就關心的是邊的個數，另一方面講呢，其實我們也可以把它理解為每一條邊上權重就把它定義成1，然後我們把它們所有的權重加起來就相當於這條路徑上面經停站的個數我就可以數出來，所以總而言之，上面所有的這些問題我們都可以統一歸納抽象成一個圖論的最短距離問題

所謂網路就是一個帶權的圖

當我們說到最短路徑問題的時候，我們其實說的不是一個問題，我們說的是一套問題，這一套問題裡面至少可以被分為兩大類，第一類叫做單源最短路徑問題，也就是說源點是固定的，我們只考慮從一個固定的源點出發，然後求從這個點到其它所有頂點的最短路徑，跟單源最短路徑對應的還有多源最短路徑問題，也就是求任意兩個頂點之間，最短的路徑，如果我已經有辦法解決單源最短路徑的問題了話，那麼為什麼不把這個演算法在每一個頂點用一邊，我自然就得到了多源最短路徑問題的解，是不是這樣呢？是這樣的，但是在某種特殊的情況下，我們會有一個更聰明的方法，會把這個問題解決的更快一點，在單源最短路徑問題裡面，我們又分兩種情況，一個是對應無權圖的，一個是對應有權圖的，可以是有向的，也可以是無向的，演算法可以從最簡單的，單源的無權圖的最短路徑開始