最短路問題專題

1、最短路問題算法及應(yīng)用 1 問題描述 2 算法介紹 2.1 dijkstra算法 2.2 floyd算法 3 應(yīng)用舉例 3.1 物流中心選址 3.2 物流配送問題 3.3 多目標(biāo)運(yùn)輸問題主要內(nèi)容定義1 對(duì)簡單圖G的每一邊e賦予一個(gè)實(shí)數(shù)，記為w(e)，稱為邊e的 權(quán)，而每邊都賦予權(quán)的圖稱為賦權(quán)圖。定義2 (u,v)-路的邊權(quán)之和稱為該路的長，而u,v間路長達(dá)到最小的 路稱頂點(diǎn)u和v的最短路。在給定賦權(quán)圖G中，求兩個(gè)互異頂點(diǎn)間的最短路，簡記為最短路問題。 最短路問題是最優(yōu)化問題之一，廣泛應(yīng)用于生產(chǎn)實(shí)踐中的許多問題，如線路安排、廠區(qū)選址、設(shè)備更新等。 1 問題描述 基本思想：按距離u0由近及遠(yuǎn)為順序，

2、依次求得u0到G的各頂點(diǎn)的最短路和距離，直到v0(或直到G的所有頂點(diǎn))，算法結(jié)束。2 算法介紹-dijkstra算法 算法步驟：初始化(i=0)：S0=vs，P(vs)=0, (vs)=0，對(duì)每一個(gè)vvs,令T(v)=+, (v)=M，k=sStep1：如果Si=V，算法終止，否則轉(zhuǎn)入step2；Step2：考察每個(gè)使(vk,vj) A且vj不屬于Si的點(diǎn)vj。如果T(vj)P(vk)+wkj，則把T(vj)修改為P(vk)+wkj，把 (vj)修改為k，否則轉(zhuǎn)入step3；Step3：令T(vji)=minT(vj)| vj不屬于Si。如果T(vji)dik+dkj，則令dij=dik+dk

3、j；Step3：若dii0，則存在一條含有頂點(diǎn)vi的負(fù)回路，停止；或者k=n停止，否則轉(zhuǎn)入step2. Matlab程序（見附件） 3.1 物流中心選址3 應(yīng)用舉例 步驟： 求出最短路徑矩陣U； 矩陣U每一行求和； 最小值行標(biāo)號(hào)為選址地點(diǎn)。參考文獻(xiàn)： F I oyd最短路徑算法在配送中心選址中的應(yīng)用，湖南農(nóng)業(yè)大學(xué)學(xué)報(bào) Matlab程序（見附件） 3.2 物流配送問題3 應(yīng)用舉例 問題抽象：物流配送問題可以抽象為必須通過指定點(diǎn)的最短路問題。 分兩種情況：車輛回到原點(diǎn)；車輛不回到原點(diǎn)。舉例：考慮2點(diǎn)的情況 由始點(diǎn)k1到終點(diǎn)k2，經(jīng)過指定點(diǎn)t1、t2的最短路經(jīng)過4個(gè)頂點(diǎn)的順序只能是如下兩種情況，k1t1t2k2和k1t2t1k2. 若要滿足所求得的路是最短路，那么4個(gè)頂點(diǎn)中相鄰頂點(diǎn)之間的路也一定是最短路。 于是分別計(jì)算k1t1，t1t2，t2k2和k1t2，t2t1，t1k2之間的最短路；然后前三者相加得d1，后三者相加得d2，比較d1與d2之值，取較小者作為最終的輸出結(jié)果。 由此可以看出，算法的時(shí)間與隨問題規(guī)模增大呈指數(shù)增長，所以最短路算法不適合大規(guī)模配送問題求解。 考慮經(jīng)過2點(diǎn)的Matlab程序（見附件）