最短路问题

最短路问题 问题描述 下图是一个有向复权图，求从 S 点出发到 T 点结束的 最短路径及其长度。 S T A1 A2 A3 B1 B2 C1 C2 6 3 3 6 6 5 8 7 4 6 7 8 9 5 6 S T A1 A2 A3 B1 B2 C1 C2 6 3 3 6 6 5 8 7 4 6 7 8 9 5 6 方法 基于动态规划的 Dijkstra 算法，其主要思想：若 P 在 S 到 T 的最短路上，则 S 到 P 的最短路径必定包含在 S 到 T 的最短路径上（P 到 T 的最短路径也必定包含在 A 到 E 的最短路径上）。 步骤 记 示 S 到 P 的最短距离，则 ( )f P ① 1 2 3 ( ) 6 ( ) ( ) f A f A f A    3 3 0 2 1 1 2 2 2 2 3 3 2( ) min{ ( ) , ( ) , ( ) } 7f B f A A B f A A B f A A B     ② 1 1 1 1 2 2 1 3 3 1( ) min{ ( ) , ( ) , ( ) } 1f B f A A B f A A B f A A B    ③ 1 1 1 1 2 2 1( ) min{ ( ) , ( ) } 15f C f B BC f B B C      2 1 1 2 2 2 2( ) min{ ( ) , ( ) } 16f C f B BC f B B C   ④ 1 1 2 2( ) min{ ( ) , ( ) } 20f T f C C T f C C T   LINGO 求解程序 model: SETS: CITIES /S,A1,A2,A3,B1,B2,C1,C2,T/: L;!属性L(i)表示 城市S到城市i的最优 行驶路线的路长; ROADS(CITIES, CITIES)/!派生集合ROADS表示的是 网络中的道路（边）; S,A1 S,A2 S,A3 !由于并非所有城市间都有道路 直接连接，所以采用稀疏集; A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T/: D;!属性D( i, j) 是城市i到j的直接距离; ENDSETS DATA: D = 6 3 3 6 5 8 6 7 4 6 7 8 9 5 6; L= 0, , , , , , , , ; !因为L(S)=0; ENDDATA @FOR(CITIES(i)|i#GT#@index(S):!这行中"@index(S)" 可以直接写成"1"; L(i) = @MIN( ROADS( j, i): L( j) + D( j, i)); );!这就是前 面写出的最短路关系式; end 结果 从后往前： 得出最短路径为： . 3 2 1S A B C   T 最短路径长度为：20. 另一种解法 假设图 有n个顶点，现需从顶点 S（1 号定点）到顶点 T（n 号顶点）的最短路. ( , )G V E 设决策变量为 ijx , 当 1ijx  , 说明边( , 位于顶点 S 至顶点 T 的路上；否则 )i j 0ijx  . 设 ij 为边( , 的长度， 其数学规划表达式为： )ji ( , ) 1 1 ( , ) ( , ) min ; 1, 1, . . 1, 0, 1, . 0,( , ) . ij ij i j E n n ij ji j j i j E j i E ij x i s t x x i n i n x i j E ,                约束的等价形式： 1 1 ( , ) ( , ) 1 1 ( , ) 1 ( , ) . . ( 1, .); 1; 1; 0,( , ) . n n ij ji j j i j E j i E n j j i j E n in i i j E ij s t x x i n x x x i j E                LINGO 求解程序 model: SETS: CITIES /S,A1,A2,A3,B1,B2,C1,C2,T/; ROADS(CITIES, CITIES)/ S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T/: w,x; ENDSETS DATA: w = 6 3 3 6 5 8 6 7 4 6 7 8 9 5 6; ENDDATA n=@size(cities); min=@sum(roads: w*x); @for(cities(i) | i#ne#1 #and# i#ne#n: @sum(roads(i,j): x(i,j)) = @sum(roads(j,i): x(j,i))); @sum(roads(i,j)|i #eq# 1 : x(i,j))=1; @sum(roads(i,j)|j #eq# n : x(i,j))=1; @for(roads(i,j):@bin(x)); end 结果