最優路徑算法

最優路徑算法是無向圖滿足通路上所有頂點（除起點、終點外）各異，所有邊也各異的通路。套用在公路運輸中，可以提供起點和終點之間的最短路徑，節省運輸成本。可以大大提高交通運輸效率。

基本介紹

• 中文名：最優路徑算法
• 定義：無向圖滿足通路上所有頂點（除起點、終點外）各異，所有邊也各異的通路

基本原理

路徑，就是無向圖滿足通路上所有頂點（除起點、終點外）各異，所有邊也各異的的通路。最優路徑就是路徑中最符合某種需求的一條路徑，比如最短路徑，就是從起點到終點的邊權值和最小的路徑。對圖求最優路徑的方法即稱為最優路徑算法，通常用計算機編程實現。

套用

在公路運輸中，為了使運輸的時間和花費最少（花費可以是油耗和費用），需要找到起點和終點的最優路徑。這條最優路徑可以是路程最短的路徑，也可以是油耗最省的路徑，依實際需求而定。在實際套用中，知道起點和終點，便可用最優路徑算法計算出路徑，這對車輛的行駛有很好的指導作用。使用計算機編程實現，更能提高效率。但類似的系統還不多見，其中ptystudio（公路運輸費用計算器）可以計算中國任意兩地間的運輸費用，使用中只要輸入起點、終點、車型等信息，ptystudio便可以根據當前成品油價和高速公路的收費計算出運輸花費，其中包括油耗、里程、公路通行費等明細。ptystudio的計算就是基於計算最優路徑的系統，計算出的花費以兩地之間最短路徑為基礎，然而該路徑的計算採用的是最優路徑算法，利用計算機實現自動化計算。