什麼是最短路徑

最短路徑是指在圖形結構中，從起點到終點經過的邊的權值總和最小的路徑。

這裏說的“圖形”可以是帶權的有向圖或無向圖，在帶權圖中，最短路徑不僅限於經過最少數量的邊，但總是選擇權值總和最小的路徑。最短路徑問題是一箇圖論中的經典算法問題，用於在圖形結構中找到兩點之間的最優連接路徑。這個問題有多種變體，包括單源最短路徑問題（找到從單一起點到所有其他頂點的最短路徑）、全局最短路徑問題（找到圖中所有頂點對之間的最短路徑）等。