Część II

Wyznaczenie najkrótszej ścieżki łączącej bazę „N” z węzłem „K” i przechodzącą przez łuk„A-B”.

W części tej wykorzystano najkrótszą drogę do węzła A wyznaczoną w części pierwszej.

Czas dojazdu do węzła A wynosi 22. Następnie przechodzimy do węzła B i szukamy najbliższej drogi do węzła K, przy czym nie przechodzimy przez łuk AB.

KROK

ETYKIETY PRÓBNE

ETYKIETY TRWAŁE

ZBIÓR WĘZŁÓW Z ETYKIETAMI TRWAŁYMI

WĘZEŁ POPRZEDNI

WĘZEŁ DOCELOWY

KOSZT DOJAZDU

WEZEŁ POPRZEDNI

WEZEŁ DOCELOWY

KOSZT DOJAZDU

1

B

B

0

B

B

0

B

B

POZOSTAŁE



2

B

Ł

12

B

L

5

B

L

5

B,L

B

V

11

3

B

Ł

12

B

V

11

L

M

5+12=17

L

J

5+6=11

L

J

11

B,L,J

4

B

Ł

12

B

V

11

B

V

11

B,L,J,V

L

M

5+12=17

J

I

5+6+8=19

J

D

5+6+5=16

5

B

Ł

12

B

Ł

12

B,L,J,V,Ł

L

M

5+12=17

J

I

5+6+8=19

J

D

5+6+5=16

V

M

11+9=20

V

O

11+13=24

6

L

M

5+12=17

J

I

5+6+8=19

J

D

5+6+5=16

J

D

5+6+5=16

B,L,J,V,Ł,D

V

M

11+9=20

V

O

11+13=24

Ł

Z

12+5=17

7

L

M

5+12=17

J

I

5+6+8=17

J

I

5+6+8=17

B,L,J,V,Ł,D,I

V

M

11+9=20

V

O

11+13=24

Ł

Z

12+5=17

D

N

5+6+5+6=22

D

M

5+6+5+15=31

D

E

5+6+5+12=28

D

C

5+6+5+10=26

8

L

M

5+12=17

L

M

5+12=17

B,L,J,V,Ł,D,I,M

V

M

11+9=20

V

O

11+13=24

Ł

Z

12+5=17

D

N

5+6+5+6=22

D

M

5+6+5+15=31

D

E

5+6+5+12=28

D

C

5+6+5+10=26

I

E

32

9

V

O

11+13=24

Ł

Z

12+5=17

Ł

Z

12+5=17

B,L,J,V,Ł,D,I,M

D

N

5+6+5+6=22

Z

D

E

5+6+5+12=28

D

C

5+6+5+10=26

I

E

32

M

O

5+12+7=24

M

C

5+12+8=25

M

D

5+12+15=32

10

V

O

11+13=24

D

N

5+6+5+6=22

D

N

5+6+5+6=22

B,L,J,V,Ł,D,I,M

D

E

5+6+5+12=28

Z,N

D

C

5+6+5+10=26

I

E

32

M

O

5+12+7=24

M

C

5+12+8=25

M

D

5+12+15=32

11

V

O

11+13=24

D

E

5+6+5+12=28

D

C

5+6+5+10=26

I

E

32

M

O

5+12+7=24

M

O

5+12+7=24

B,L,J,V,Ł,D,I,M

M

C

5+12+8=25

Z,N,O

N

C

5+6+5+6+9=31

N

E

5+6+5+6+10=32

N

F

5+6+5+6+7=29

N

G

5+6+5+6+10=32

12

D

E

5+6+5+12=28

D

C

5+6+5+10=26

I

E

32

M

C

5+12+8=25

M

C

5+12+8=25

B,L,J,V,Ł,D,I,M

N

C

5+6+5+6+9=31

Z,N,O,C

N

E

5+6+5+6+10=32

N

F

5+6+5+6+7=29

N

G

5+6+5+6+10=32

O

C

5+12+7+6=30

O

P

5+12+7+9=33

O

U

5+12+7+12=36

13

D

E

5+6+5+12=28

D

E

5+6+5+12=28

B,L,J,V,Ł,D,I,M

I

E

32

Z,N,O,C,E

N

E

5+6+5+6+10=32

N

F

5+6+5+6+7=29

N

G

5+6+5+6+10=32

O

P

5+12+7+9=33

O

U

5+12+7+12=36

C

P

5+6+5+9+5=36

C

G

5+6+5+9+8=39

14

N

F

5+6+5+6+7=29

N

F

5+6+5+6+7=29

B,L,J,V,Ł,D,I,M

N

G

5+6+5+6+10=32

Z,N,O,C,E,F

O

P

5+12+7+9=33

O

U

5+12+7+12=36

C

P

5+6+5+9+5=36

C

G

5+6+5+9+8=39

15

N

G

5+6+5+6+10=32

N

G

5+6+5+6+10=32

B,L,J,V,Ł,D,I,M

O

P

5+12+7+9=33

Z,N,O,C,E,F,G

O

U

5+12+7+12=36

C

P

5+6+5+9+5=36

C

G

5+6+5+9+8=39

F

G

29+8=37

F

K

34

16

O

P

5+12+7+9=33

O

P

5+12+7+9=33

B,L,J,V,Ł,D,I,M

O

U

5+12+7+12=36

Z,N,O,C,E,F,G

C

P

5+6+5+9+5=36

P

F

K

34

G

H

32+11=43

G

K

32+12=44

G

T

32+7=39

17

O

U

5+12+7+12=36

F

K

34

F

K

34

B,L,J,V,Ł,D,I,M

G

H

32+11=43

Z,N,O,C,E,F,G

G

K

32+12=44

P,K

G

T

32+7=39

P

G

33+10=43

Zestawienie najkrótszych połączeń z węzła N do węzła K przechodzących przez łuk A-B

Lp.	WĘZEŁ		KOSZT DOJAZDU
		POPRZEDNI			DOCELOWY
1	N	N	0
2	N	C	9
3	C	O	15
4	O	A	22
5	A	B	32
6	B	L	37
7	L	J	43
8	J	D	48
9	D	N	54
10	N	F	61
11	F	K	66

---