用於計算一個節點到其他所有節點的最短路徑。主要特點是以任一起始點為原點，沿權值最小的路徑向其它節點擴展，直到將全部節點包含進最小路徑集。
基本介紹
- 中文名：最短權路徑
- 外文名：The most short path
- 學科：離散數學
基本思想,舉例,
基本思想
已知圖G=（V，E），我們希望找出從某任一結點Vi∈V到V中的每個結點的最短路徑。
先任取一點V0，選擇V0到周邊各點中最短路徑的一點V1，將d(V0,V1)加入最短路徑集d(S)，V1加入點集S，然後選擇V1到周邊各點中最短路徑的一點V2，將d(V0,V2)加入最短路徑集d(S)，V2加入點集S，如此不斷將新點和最短路徑加入點集和最短路徑集，直到Vk只有到點集S={V0，V1，……，Vk-1，Vk}的路徑，這時將Vk-1選作起點，看有沒有到除去點集S={V0，V1，……，Vk-1，Vk}其他點的最短路徑，如果有將d(Vk-1,Vk+1)加入最短路徑集d(S)，Vk+1加入點集S，如果沒有選擇Vk-2作為起點，再看有沒有到除去點集S={V0，V1，……，Vk-1，Vk}其他點的最短路徑，如此反覆，直到S點集包含全部點並且最後一條路徑是從點集{V0，V1，……，Vn-1，Vn}到{V0，V1，……，Vn-1，Vn}。任意兩點Vi, Vj最短權路逕取最短路徑集兩點所經過點的最短路徑和與兩點直接路徑的最小值即D(Vi, Vj)=min{
，d(Vi, Vj)}
舉例
一公司在六個城市c1，c2，…，c6中的每一個都有分公司。從ci到cj的班機旅費由下列矩陣中的第i行第j列元素給出(∞表示沒有直接班機)：
0 50 ∞ 40 25 10
50 0 15 20 ∞ 25
∞ 15 0 10 20 ∞
40 20 10 0 10 25
25 ∞ 20 10 0 55
10 25 ∞ 25 55 0
公司所關心的是計算兩城市間的最便宜路線的表格。
由最短權路徑可知，C1←→C6最小權為10，C6←→C2最小權為25，C2←→C3最小權為15，C3←→C5最小權為20，C3←→C4最小權為10,C4←→C2最小權為20
C1C2C3C4C5C6C103550402510C250015205025C350150102040C440201001025C525502010055C610254025550
