最短路徑簡介

1、從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法等。

2、定義：最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。演算法具體的形式包括：確定起點的最短路徑問題- 即已知起始結點，求最短路徑的問題。適合使用Dijkstra演算法。

3、確定終點的最短路徑問題- 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。

4、確定起點終點的最短路徑問題- 即已知起點和終點，求兩結點之間的最短路徑。全域性最短路徑問題- 求圖中所有的最短路徑。適合使用Floyd-Warshall演算法。