[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [ 100 ] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

Lex.


.

Poa.

. 6.2.3. LEX.

V0.

G; set

LEX BED, LEX . , , .

, .

Algorithm DIJKSTRA D1ST(W?) V0 W G , . 0. [ ] V0 «»; and «». 1. [ ] Set D1ST (U) - (V0, V) DIST (V0) 0; and set NEXT - 2. [] While XTW do through, 4 od; and STOP. 3. [ «» ] «» set DIST (t/) - ) {U) DIST(NEXT)+(NEXT, U). 4. [ «» ] U - , DIST(t/) - «» ; U «»; and set NEXT U.

DIJKSTRA . .

6.2.1. DIJKSTRA V0 W.

. , 3 4 V, «», DIST () . , «» U DIST (t/) V0 U, , U.

=0 1 , . . V0, DISTVO)=0, ,



V0 . , «» DIST(t/), , V0 , . . , «».

, , , (+1)- 3. , «» U DIST{t/) V0 U, «» , .

, , . . «» U V0 U, U - «» , , , m<DIST(f/). - «» , . , DIST(6) «» - m=DIST(6). , <15().

SUBROUTINE DIJKST (A.M.V0,W,FROH,TO,LENGTH,EDGES)

\ W

- G ,

(NUHERISCHE: KATHEMATIC.V 1.

269-271). -

, (. (

1972). 422}, -

V0.

==

A(J,JJ , J J ,

, .

(1 ,J) = .1 ,

.

VC

W

G 1......,

- 2.UE.H.UE.100

FnOM(l) 1-

0(1 0 =FROM( 11=

LENGTHdl =( 1)= e.LENGTH{l)=.

EDGES .

. 6.2.4. DIJKSTRA.



i

CIST(I)

NEXT

UNDETIDB

;!

UNDETtI)

VERTEXtl) - , 11 UNDETtI) V0.

INTEGER AdOO.lOO),H,W,W,FnOH{100j,TO{100),LENGTH(10D) INTEGER EDGES,DIST(1tlO),NEXT,NUHUN,UET{100J JNTECER VERTEXllOO)

EDGES e 0

NEXT e W>

NUMUN " H-1

£0 1D0 1 a 1,H

UNDETd) 1

BlST(l) «A(VO,l)

VERTEX(l) VO

JOD CONTINUE

; UNDET() e H

IllST(VO) =I)IST(H)

CO TO 350

-1

I -i.NUHUH 1 -

J»UNDET(I) N (-2){-1)/2

JK L + A(NEXT,J) N {H-2)(H-11/2

«F(DIST{I) .LE. JK) GO TO 300 N.A (H-2)(H-11/2.E

VERTEX(l) « NEXT F

EIST(I) » OK F

CONTINUE ,,, V , (--/

. 6.2.4.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [ 100 ] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0011