店鋪選址最短路徑與選址問題-全文預(yù)覽
【正文】 一。因為 (v5， v6)， (v5 ， v7)∈ E， 而且 v6和 v7都是 T標(biāo)號，故修改它們的 T標(biāo)號為 T(v6)＝ min[T(v6)， P(v5)+w56]＝ min[9， 7+1]= 8 T(v7)＝ min[T(v7)， P(v5)+w57]＝ min[+∞， 7+7]=14 ② 在所有 T標(biāo)號中， T(v6)＝ 8最小，于是令：P(v6)＝ 8。因為 (v4， v5)∈ E，而且 v5是 T標(biāo)號，故修改 v5的 T標(biāo)號為 T(v5)＝ min[T(v5)， P(v4)+w45]＝ min[+∞， 3+5]＝ 8 ② 在所有的 T標(biāo)號中， T(v3)＝ 4最小，故令 P(v3)＝ 4。因為 (v1， v2)， (v1， v3)， (v1， v4)∈ E， 而且 v2， v3， v4是 T標(biāo)號，所以修改這 3個點的 T標(biāo)號為 T(v2)＝ min[T(v2)， P(v1)+w12]＝ min[ +∞， 0+2]＝ 2 T(v3)＝ min[T(v3)， P(v1)+w13 ]＝ min[ +∞， 0+5]＝ 5 T(v4)＝ min[T(v4)， P(v1)+w14 ]＝ min[ +∞， 0+3]＝ 3 ② 在所有 T標(biāo)號中， T(V2)＝ 2最小，于是令 P(V2)＝ 2。試求城鎮(zhèn) v1到 v7之間的最短路徑。 ② 若 G中沒有 T標(biāo)號，則停止。其中，每一個頂點的 T標(biāo)號表示從起點 v1到該點的最短路徑長度的上界，這種標(biāo)號為臨時標(biāo)號； P標(biāo)號表示從 v1到該點的最短路長度，這種標(biāo)號為固定標(biāo)號。 .n標(biāo)號法的基本思想 設(shè) G是一個賦權(quán)有向圖，即對于圖中的每一條邊，都賦予了一個權(quán)值。 不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。 在路徑的優(yōu)選計算問題中，最常見的是最短路徑問題；而在頂點的優(yōu)選計算問題中，最為常見的是中心點和中位點選址問題。最短路徑與選址問題 216。其中，最為常見的是關(guān)于路徑和頂點的優(yōu)選計算問題。那么，各個港口之間最廉價的貨運線路是什么？一、最短路徑問題（一）最短路徑的含義n “ 時間 ” 意義上的最短路徑 例如，某家經(jīng)營公司有一批貨物急需從一個城市運往另一個城市，那么，在由公路、鐵路、河流航運、航空運輸?shù)?4種運輸方式和各個運輸線路所構(gòu)成的交通網(wǎng)絡(luò)中，究竟選擇怎樣的運輸路線最節(jié)省時間？ 以上 3類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。 n 標(biāo)號法優(yōu)點 不僅可以求出起點到終點的最短路徑及其長度，而且可以求出起點到其他任何一個頂點的最短路徑及其長度 ； 同時適用于求解有向圖或無向圖上的最短路徑問題。這些標(biāo)號，又進(jìn)一步區(qū)分為 T標(biāo)號和 P標(biāo)號兩種類型。n標(biāo)號法具體計算步驟
法律信息相關(guān)推薦
鄂ICP備17016276號-1