АЛГОРИТМ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ ДЛЯ РАЗРЕЖЕННЫХ ГРАФОВ БОЛЬШОЙ РАЗМЕРНОСТИ

  • Published on
    04-Apr-2017

  • View
    215

  • Download
    2

Embed Size (px)

Transcript

  • 2013

    1(19)

    519.178

    .. , ..

    , . ,

    E-mail: urakov@ufanet.ru, timeryaev@yandex.ru

    - . - , . - .

    : , APSP, , , , .

    (APSP

    All-Pairs Shortest Path problem) . - , ( , ) . , - , , , : -

    / ? / ?

    - , . 106 , . , .

    APSP , , - . - APSP , . , [1], [2], [3], [4], [5].

    APSP . - , - . - .

  • 85

    1. 1.1.

    - G = (V,E,w) , V = {v1, v2, . . . , vn} ; E = {e1, e2, . . . , em} V V - ; w : E [0,) . - vi vj e(vi, vj). .

    ( ), - . vi vj - w (i, j), vi vj, , w (i, j) = . d (vi) vi , vi. -, m n2.

    v0, e1, v1, . . . ,vk1, ek, vk, - . . psij = ps(vi, vj) vi vj vi vj . m (i, j) vi vj vi vj (m (i, i) = 0, i = 1, . . . , n). - Mnn mij = m(i, j). , , mij |Vp+1|, p = 0, . . . , r 1. vp+1i Gp+1, vpi Gp, ep+1

    (vp+1j , v

    p+1k

    )-

    Gp+1, ep(vpj , v

    pk

    ) Gp. , -

    vp1, vp2, . . . , v

    pk Gp,

    Gp+1 = Rp (vp1, v

    p2, . . . , v

    pk). : wp+1(i, j) = wp(i, j)

  • 86 . . , . .

    i, j, , vp+1i , vp+1j Vp+1. v

    pi v

    pj Gp

    mp(i, j), Mp =(mpij). , -

    Api vpi Gp.

    1.2. .

    G = (V,E,w) w : E [0,). , . . M - P .

    2. 2.1.

    . - :

    1) ;2) -

    ;3)

    ; . : )

    ; ) c e , - .

    , , , , [6]. .

    , , . - , , , ( ). , [6] (point-to-point), -, APSP .

    2.2.

    G0 = (V0, E0, w0) G0 - S = {G1, G2, . . . , Gr}. , Gp+1 S Gp .

    vpi Gp k, . . - vpiz , z = 1, . . . , k. - vpi ( v

    pi ),

    vpij , ep(vpij , v

    pi ), v

    pi , e

    p(vpi , vpil), vpil , j, l {1, 2, . . . , k}. , -

  • 87

    vpi , vpi .

    wmv(1,2,...,h)p (ij, il) = ming=1,2,...,h

    (wp (ij, g) + wp (g, il))

    , vpij vpil

    vp1, vp2, . . . , v

    ph Gp. (

    vpij , vpil

    ), vpi Gp+1 ,

    wp+1 (ij, il) =

    {min

    (w

    mv(i)p (ij, il) , wp (ij, il)

    ), wmv(i)p (ij, il) < w

    mv(h6=i)p (ij, il) ,

    wp (ij, il) .(1)

    P nn pij = .

    P , wmv(i)p (ij, il) < min

    (wp (ij, il) , w

    mv(h6=i)p (ij, il)

    ),

    p

    ijil=

    {vi, p

    iil

    =,piil, p

    iil6=.

    (2)

    , vpi Gp, ( vpi ), vpi .

    dmax , nmin Gr Imax . dmax,nmin Imax , .

    vpi k -. I (vpi ) - vpi . v

    pi k,

    I (vpi ) = k. (1) (vpij , v

    pil

    ) vpi I (v

    pi )

    I (vpi ) =

    {I (vpi ) + 1, wp (ij, il) = & w

    mv(i)p (ij, il) < w

    mv(h6=i)p (ij, il) ,

    I (vpi ) .(3)

    , Gp+1 Gp vpi . I (v

    pi ) > 0, -

    , . (3) - Imax : vpi , I (v

    pi ) 6 Imax.

    . dmax > 2 3 , 1 dmax. - , dmax. vpi . - d

    (vpj)6 dmax,

  • 88 . . , . .

    vpi , . - . 1 2 .

    1.

    : G0 = (V0, E0, w0), |V0| = n; dmax, nmin, Imax; Pnn =

    (pij

    ), pij =

    i, j = 1, . . . , n. 0. dc = 1, i = 0, nc = n, p = 0. 1.

    1: nc = nmin, 2: ,3: 4: vpj Vp (j > i & d

    (vpj)

    = dc), 5: i = j, 2,6: 7: dc < dmax, 8: dc = dc + 1, i = 0 1,9:

    10: . 2.

    11: (vpi , nc, Imax, dmax, nmin, p, P), 1.

    12: : Gr = Gp.

    2.3. APSP Gr S, -

    . Mr Gr. M r = Mr P

    p

    ij =

    {prij, p

    ij = & p

    prijj

    =,pprijj, p

    ij = & p

    prijj6=;

    (4)

    p

    ij =

    {prij, wr(i, j) > m

    rij & p

    prijj

    =,pprijj, wr(i, j) > m

    rij & p

    prijj6=,

    (5)

    prij Pr Gr. - Gr , , , . mrij = mrij = m0ij i, j, , vri , vrj Vr.

    Gr |Vr| = 1, - .

    2.4. ( 3) -

    S = {G0, G1, . . . , Gr}. G0 , Gr -,

  • 89

    2.

    : vpi , nc, Imax, dmax, nmin, p, P .

    1. 1: d (vpi ) < 3, 2: 2,3: 4: I (vpi ) = d (v

    pi ). A

    pi

    I (vpi ) (3).5: I (vpi ) 6 Imax, 6: 2,7: 8: .

    2. 9: Gp+1 = Rp (vpi ).

    10: Gp+1, Api , (1).

    11: P (2), nc = nc 1, t = p, p = p+ 1.12: nc = nmin, 13: ,14: 15: nc > nmin16: vpil , , d

    (vpil)< d

    (vtil),

    17: (vpil , nc, Imax, dmin, nmin, p, P).

    . Gr G0 Gr1, Gr2, . . . , G1 p vrpi ,, vrp+1i / Vrp+1 v

    rpi Vrp.

    vr1i , Gr Gr1, vr1iz , z = 1, . . . , k, Gr1. Gr - , . . M r = Mr. - M r1 Gr1, v

    r1i

    Gr1, Mr1 -

    M r: mr1jl = m

    rjl vrj , vrl Vr.

    Gr1 vr1i - vr1iz , z = 1, . . . , k, v

    r1i v

    r1l

    Gr1

    mr1 (i, l) = min

    z{1,...,k}

    (wr1 (i, iz) +m

    r (iz, l)).

    M rp Grp+1 - Grp c vrpi :

    mrpjl = m

    rp+1jl , v

    rp+1j , v

    rp+1l Vrp+1; (6)

    mrpil = m

    rpli = min

    z{1,...,k}

    (wrp (i, iz) +m

    rp+1 (iz, l)), vrp+1l Vrp+1. (7)

  • 90 . . , . .

    x(l) iz l, (7). P , wrp(i, l) > m

    rpil wrp(l, i) > m

    rpli ,

    pil = p

    li =,

    p

    il =

    {vi, p

    x(l)l =,p

    x(l)l, p

    x(l)l 6=;(8)

    p

    li =

    {vl, p

    x(l)i =,p

    x(l)i, p

    x(l)i 6=.(9)

    3.

    : S = {G0, G1, . . . , Gr}, Mr, P

    1: p = 1.2: p 6 r3: M rp (6), (7) P

    (8) (9);p = p+ 1.

    4: : M 0, P .

    2.5. 1. -

    , . . M 0 P

    G0.. M 0.

    - , (1). - ( G0) : m

    rjl = m

    0jl

    vrj , vrl Vr. -

    ; , Gr Gr1 Gr1 ( - (6) vr1i Gr1). Gr1 , - , . . (7).

    P . , Gr - P . Gr ps (vj, vl) vj vl prij, . . . , vl. (2), p

    prijj

    =, ps(prij, vj

    ) , prij vj, . . pij = prij. p

    prijj6=, , (2),

    ps(prij, vj

    )= prij, . . . , p

    prijj, e(p

    prijj, vj), vj, . . pij = p

    prijj

    . (4), (5) - pjl, vrj , vrl Vr, , . pjl 6= wr(j, l) = mrjl (2) , . . pjl = pjl vrj , vrl Vr.

    , P , Gr Gr1 P

    vr1i . Gr1,

  • 91

    P vrj , vrl Vr , - , . . (8), (9).

    3. Intel Core 2 Duo E8400

    3 2 32- Windows XP. - C++ Borland C++Builder 6. (G1G10) [7]. G1G10 103 104 10 . -. (GR, . [8]). . 1.

    1

    - - . G1 103 2,5 103 2,48 6

    10

    G2 2 103 5,21 103 2,6 5G3 3 103 7,88 103 2,62 6G4 4 103 1,07 104 2,68 6G5 5 103 1,33 104 2,66 6G6 6 103 1,58 104 2,63 7G7 7 103 1,85 104 2,64 6G8 8 103 2,08 104 2,6 6G9 9 103 2,36 104 2,62 7G10 104 2,72 104 2,72 7GR 2,1 103 6 103 2,86 14 20

    dmax = Imax = , nmin = 1. , Gr - . . ( ) - ( , [4]), . . 2.

    - 47 . , 34 - . S = (G1, G2, . . . , Gr) 17, - .

  • 92 . . , . .

    2

    , ,

    ,,

    , .,

    , .,

    ./,

    , .

    . .G1 0,03 1,5 0,05 1,7 50 11G2 0,13 6,7 0,14 7,1 52 12G3 0,31 16 0,33 17 52 12G4 0,67 30 0,88 32 45 22G5 1,1 48 1,2 52 44 16G6 1,5 72 1,8 82 48 20G7 2,1 97 2,2 104 46 17G8 2,6 131 2,8 145 50 21G9 3,7 177 4,7 189 48 24G10 5,4 218 6,4 230 40 23GR 0,17 7,5 0,4 18,8 45 17

    -

    . . , , ( 47 ) , .

    , - - . - - .

    1. Bellman R. On a routing problem // Quarter. Appl. Math. 1958. No. 16. P. 8790.2. Floyd R.W. Algorithm 97: Shortest Path // Comm. ACM. 1962. No 5(6). P. 345.3. Dijkstra E.W. A note on two problems in connexion with graphs // Numer. Math. 1959. No. 1.

    P. 269271.4. .. . : . .: , 2006. 1296 .5. Johnson D.B. Efficient algorithms for shortest paths in sparse graph // J. ACM. 1977. No. 24.

    P. 113.6. Geisberger R., Sanders P., et al. Contraction hierarchies: faster and simpler hierarchical routing

    in road networks // International Workshop on Experimental Algorithms (WEA 2008).Provincetown: Springer, 2008. P. 319333.

    7. http://www.dis.uniroma1.it/challenge9/download.shtml 9th DIMACS Implementa-tion Challenge Shortest Paths ( : 2012).

    8. .., .. // . 2012.2. C. 9599.

Recommended

View more >