新建 文本文档 (10).txt

最短路径问题 动态规划法求解多段图单源最短路的VB程序清单

1．最短路径问题
(１)问题描述
设有如图所示有向图，边上的数字代表结点之间的距离，S1，S2，S3，S4，S5为起点，T1，T2，T3，T4，T5代表终点，试找出一条从起点到终点的最短路径。

如图中所指出的S4->A3->B3->C2->T3最短路径的长度为26。



（2）算法分析
当图中结点比较多，同时深度较深时，采用遍历算法时间上是不可取的。所以动态规划的方法适合本题。
·有向图的数据结构可用数组d表示:
实数类型三维数组d（N，M，3）
d（I，J，1）表示点（I，J）--（I-1，J+l)距离
d（I，J，2）表示点（I，J）--（I，J+l)距离
d（I，J，3）表示点（I，J）--（I+1，J+l)距离
即d数组的第一维表示行，d数组的第二维表示列，d数组的第三维表示点到另三个方向（右上、右边、右下）上的点的距离。

此时 d(1，1，1)=max，d(1，1，2)=3，d(1，1，3)=max     { max 表示无通路 }
d(2，1，1)=7，d(2，1，2)=6，d(2，1，3)=max
d(5，1，1)=4，d(5，1，2)=max，d(5，1，3)=max
d(1，2，1)=max，d(1，2，2)=6，d(1，2，3)=7
d(2，2，1)=max ，d(2，2，2)=8，d(2，2，3)=12
max表示无通路

·算法的过程:从倒数第二列开始(C1，C2，C3，C4)，当路径到达C1时，以下的最短为min(14，15)=10；同时记录下走的方向，为此，我们定义数组e:
三维实型数组e(N，M，2)
其中 e(I，J，1)表示从此点到达下一个点的最短路径;e(I，J，2)表示从此点到达下一个点的最短路径的方向:
1表示(I-1，J+1)，2表示(I，J+1)，3表示(I+1，J+1)
由此可知，最后一层的算法为:

    FOR I=1 to N
                从d(I，4，1)，d(I，4，2)，d(I，4，3)中找出最小值；
        e(I，4，1)=最小值，e(I，4，2)=方向
NEXT  I

在计算倒数第三列(B1，B2，B3，B4，B5)时:
如B3点计算为 mIn[(B3，C2)点距离+C2点最小值，(B2，C3)距离+C3点最小值]
由此可以得到一个统一的算法:
    FOR I=M-1 TO 1 STEP -1
     FOR J=1 TO N
求出d(I，J，1)+e(I-1，J+1，1)
        d(I，J，2)+e(I，J+1，1)
          d(I，J，3)+e(I+1，J+1，1)
NEXT J
NEXT I
其中的最小值填入e(I，J，1)，e(I，J，2)方向为0，1或2。
在e(I，J)求出之后，再在e(1，1，2)，……，e(2，1，1)，e(I，1，1)中找出最小值，记为e(I，1，1)，即第一列上的点的最短路径，然后求出达到最短路径的通路:
当d(I，1，2)=1时:I-1，2
当d(I，1，2)=2时:I，2
当d(I，1，2)=3时:I+1，2
以此方法，求出通路。


（3）程序清单


DECLARE SUB outputok ()
DECLARE SUB make ()
DECLARE FUNCTION getn! (mm!)
DECLARE SUB readfile ()
CONST maxn = 20, maxm = 20, filename = "q11.txt"
DIM d(maxn, maxm, 3) AS SINGLE
DIM e(maxn, maxm, 2) AS SINGLE
DIM n, m AS INTEGER
CALL readfile
CALL make
CALL outputok
END

FUNCTION getn (mm)
IF mm / 2 = INT(mm / 2) THENgetn = n - 1ELSEgetn = nEND IFEND FUNCTION

SUB make
DIM i, j, k, p AS INTEGER
DIM o, no AS SINGLE
FOR j = m - 1 TO 1 STEP -1
FOR i = 1 TO getn(j)
o = 1E+10
p = o
FOR k = -1 TO 1
no = e(i + k, j + 1, 1) + d(i, j, k + 2)
IF no < o THENp = k: o = no
END IF
NEXT k
e(i, j, 1) = o
e(i, j, 2) = p
NEXT i
NEXT j
END SUB

SUB outputok
DIM i, j, p AS INTEGER
p = 1
FOR i = 2 TO n
IF e(i, 1, 1) < e(p, 1, 1) THEN
p = i
END IF
NEXT i
PRINT "Min Length=", e(p, 1, 1)
PRINT "Trail is ", "S" + trim(str(p));
FOR i = 1 TO m - 1
PRINT "->";
IF i < m - 1 THEN
PRINT chr(64 + i)
ELSE
PRINT "T"
END IF
p = p + trim(e(p, i, 2))
PRINT p;
NEXT i
PRINT
END SUB

SUB readfile
DIM i, j, k AS INTEGER
OPEN filename FOR INPUT AS #1
INPUT #1, n, m
FOR i = 1 TO n
FOR j = 1 TO m
FOR k = 1 TO 3
INPUT #1, d(i, j, k)
IF d(i, j, k) = 0 THEN
d(i, j, k) = 1E+08
END IF
NEXT k
NEXT j
NEXT i
CLOSE (1)
END SUB

INPUT:

5 5
0 3 0 0 6 7 0 8 0 0 14 10 0 0 0
7 6 0 0 8 12 6 12 0 0 15 10 0 0 0
5 6 0 0 4 16 6 14 0 0 12 6 0 0 0
6 2 0 0 8 7 8 13 0 0 8 6 0 0 0
4 0 0 0 0 0 12 0 0 0 0 0 0 0 0

OUTPUT:

Min Length = 7

Trail is     S4 -> A4 -> B4 -> C3 -> T4