有向圖最短路徑

有向圖（Directed Graph）中最短路徑問題是指在圖中找到兩個頂點之間的距離最短的路徑。這裡的距離通常是指經過邊的數量，但也可能是其他意義下的距離，例如權重和等。有向圖中最短路徑問題可以分為單源最短路徑問題（Single-Source Shortest Paths）和多源最短路徑問題（All-Pairs Shortest Paths）。

單源最短路徑問題是指給定一個有向圖和一個源點，找出從這個源點到所有其他頂點的最短路徑。這可以用貪心算法（如Dijkstra's algorithm）或動態規劃算法（如Bellman-Ford algorithm）來解決。

多源最短路徑問題是指給定一個有向圖，找出所有頂點對之間的最短路徑。這通常比單源最短路徑問題更難，可以用Floyd-Warshall algorithm或Johnson's algorithm來解決。

在實際應用中，有向圖最短路徑問題可以用來解決交通路線規劃、網絡流量最佳化、機器人運動規劃等問題。