§10.2最短路问题 def6:设G=(V,A,W)为一个赋权有向图, V为指定发点,V为指定收点,其余为中间点, P为G中以s到V的一条有向路,则称 wd∑vo为路P的长度,若有 mQ则称回为G中从v到v的最 短路W印为该最短路的长度(此中F为G中 所有从到V的全体有向路的集合)
12 § 10.2 最短路问题 def 6：设G =（V, A, W）为一个赋权有向图， Vs为指定发点，Vt为指定收点，其余为中间点， P为G中以Vs到Vt的一条有向路，则称 为路P的长度，若有 则称 为G中从Vs到Vt的最 短路， 为该最短路的长度（此中F为G中 所有从Vs到Vt的全体有向路的集合）。 aP W(P)def W (a) ) min ( ) ~ W(P W P PF = P ~ P) ~ W(
最短路问题在企业厂址上选择,厂址布 局,设备更新,网络线路安装等工程设计与 企业管理中有重要应用
13 最短路问题在企业厂址上选择，厂址布 局，设备更新，网络线路安装等工程设计与 企业管理中有重要应用
(一) Bellman最优化原理 1命题1:若P是网络G中从V到V的一条最小路, V是P中除V与V外的任何一个中间点,则沿P 从V到的一条路P1亦必是V到V的最小路
14 （一）Bellman最优化原理 1 命题1：若P是网络G中从Vs到Vt的一条最小路， Vl是P中除Vs与Vt外的任何一个中间点，则沿P 从Vs到Vl的一条路P1亦必是Vs到Vl的最小路。 Vs V1 V Vl 2 P Vt 2 P1
●证明(反证): 若P1不是从V到V的最小路,则存在另一条 到V的路P2使W(P2)<W(P1,若记路P中从V到 V的路为P3。则有W(P2)+W(P3)<W(P1)+ w(P3)=W(P),此说明G中存在一条从沿P2到 V沿P3再到v的更小的一条路,这与P使G中从 V、到V的一条最小路矛盾
15 ⚫ 证明（反证）： 若P1不是从Vs到Vl的最小路，则存在另一条 Vs 到Vl的路P2使W(P2 )<W(P1 )，若记路P中从Vl到 Vt的路为P3。则有W(P2 ) + W(P3 )<W(P1 ) + W(P3 )=W(P)，此说明G中存在一条从Vs沿P2到 Vl沿P3再到Vt的更小的一条路，这与P使G中从 Vs到Vt的一条最小路矛盾
2算法思想: 设G中从V到V的最小路P:V 则由上述命题知:P不仅是从到V的最小路 而且从V到P中任意中间点的最短路也在P上, 为此可采用如下求解思路: (1)为求得V到v的最短路,可先求得V到中间点 的最短路,然后由中间点再逐步过渡到终点vt
16 2 算法思想： 设G中从Vs到Vt的最小路P：Vs…Vj…Vk…Vt， 则由上述命题知：P不仅是从Vs到Vt的最小路， 而且从Vs到P中任意中间点的最短路也在P上， 为此可采用如下求解思路： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点 的最短路，然后由中间点再逐步过渡到终点Vt