摘要
所有的圖都是有最短路徑的，計算最短路徑比較經典的應用場景就是路徑規劃。最短路徑也有它自身的局限性，比如不能出現負權環等。這裡先了解最短路徑的概況，後面幾期将分别介紹求最短路徑的幾個經典算法。
在有權值的圖中，可以找到最短路徑，即指兩頂點之間權值之和最小的路徑，有向圖和無向圖都是可以找到最短路徑的。如下圖所示：
上面兩個圖就是有向圖和無向圖中頂點 A 到不同頂點的最短路徑。
那麼無權圖有沒有最短路徑呢？答案也是有的。
無權圖中的每一個邊的權值可以想象成 1，那麼每一個邊的權值都是一樣的。所以無權圖的最短路徑取決于該頂點到另外一個頂點途徑邊的數量。
負權邊有權圖中，存在邊的權值是負數時，被稱為負權邊。尋找圖的最短路徑中，是允許有負權邊，但是不被允許存在負權環。因為負權環會讓路徑一直循環，權值一直無限遞減下去，如下圖所示：
左側圖中，頂點A到頂點E是 -20，是被允許的。右側圖，頂點E到頂點C是-10，是不被允許的，因為頂點E、C、D 形成了一個環，并且是負權環（即三個邊權值加起來是負值），在持續的循環下，權值會不斷遞減，是不合理的。
算法應用最短路徑最多的場景就是路徑規劃。處理最短路徑的算法主要分為兩類，一類是單源最短路徑，就是确定一個頂點，求該頂點到其他邊的最短路徑。另外一類就是多源最短路徑，就是可以求出任意的兩個頂點之間的最短路徑。不同的類别都對應的有經典的算法：
- 單源：Dijkstra(迪傑斯特拉算法)、Bellman-Ford(貝爾曼-福特算法)
- 多源：Floyd(弗洛伊德算法)
看算法的名稱，就大概明白算法都是以發明者的名字來命名的。不同的算法都有各自的特點和局限性，在實際應用中要根據自己的需求來選擇。最高級的是理解算法的邏輯，能夠觸類旁通，後面幾期将分别介紹這幾個算法。
總結,
- 所有的圖都是有最短路徑的，不管有向圖還是無向圖；
- 圖中的權值是允許存在負權邊的，但是不允許存在負權環；
- Dijkstra、Bellman-Ford 和 Floyd 都是獲取最短路徑的經典算法；
更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
