最短路徑問題

最短路徑問題是圖論中的一個經典問題。

套用

找出圖中兩個頂點間的最短路徑。

分類

可分成兩個子問題，即單源最短路徑問題和所有頂點對之間的最短路徑問題。前者是找出從某一頂點出發到圖中所有其他頂點的最短路徑，主要算法有迪克斯徹算法等；後者是求圖中每一對頂點之間的最短路徑，主要算法有弗洛伊德算法等。