ETYKIETY PRÓBNE			ETYKIETY TRWAŁE			ZEST.WĘZŁÓW
KROK	WĘZEŁ		KOSZT	WĘZEŁ		KOSZT	O ETYKIETACH
	POPRZEDNI	NASTĘPNY	DOJAZDU	POPRZEDNI	NASTĘPNY	DOJAZDU	TRWAŁYCH
1	N N	N POZOST.	0 ∞	N	N	0	N
2	N N N N N	K r g t c	5 8 6 10 11	N	K	5	N,K
3	N N N N K K	r g t c p r	8 6 10 11 6+5 7+5	N	g	6	N ,K ,g
4	N N N K K G G g	r t c p r r n x	8 10 11 5+6 5+7 6+9 6+6 6+14	N	r	8	N,K , g, r
5	N N K r r r g g	t c p o w n n x	10 11 5+6 8+10 8+8 8+12 6+6 6+14	N	t	10	N, K, g, r, t
6	N K r r r g g t	c p o w n n x c	11 5+6 8+10 8+8 8+12 6+6 6+14 10+10	N	c	11	N, K, g, r, t, c
7	c g g r r r k	x x n n w o p	11+9 6+14 6+6 8+12 8+8 8+10 5+6	K	p	11	N K, g, r, t, c, p
8	p p r r r g g c	i o o w n n x x	11+9 11+5 8+10 8+8 8+12 6+6 6+14 11+9	g	n	12	N, k, g, r, t, c, p, n
9	p p r r g c n n n n n	i o o w x x x z m u w	11+9 11+5 8+10 8+8 6+14 11+9 12+6 12+10 12+11 12+5 12+6	p	o	16	N, k, g, r , t, c, p, n, o
10	o o o p r g c	i w j i w x x	16+6 16+11 16+7 11+9 8+8 6+14 11+9	r	w	16	N, k, g, r , t, c, p, n, o, w
11	p o o w w n n n n g c	i i j j u u m z x x x	11+9 16+6 16+7 16+8 16+10 12+5 12+11 12+10 12+15 6+14 11+9	n	u	17	N, k, g, r , t, c, p, n, o, w, u
12	p o o w n n n g c u u u u	i i j j m z x x x j A l m	11+9 16+6 16+7 16+8 11+12 10+12 12+15 6+16 11+9 17+9 17+7 17+9 17+5	c	x	20	N, k, g, r , t, c, p, n, o, w, u, x
13	p o o w u u u u n n x	i i j j j l A m m z z	11+9 16+6 16+7 16+8 17+9 17+9 17+7 17+5 12+11 12+10 20+9	p	i	20	N, k, g, r , t, c, p, n, o, w, u, x, i
14	i i o w u u u u n n x	d e j j j A l m m z z	20+7 20+10 16+7 16+8 17+9 17+7 17+9 17+5 11+12 12+10 20+8	n	m	22	N, k, g, r, t, c, p, n, o, w, u, x, i, m

15	i i o w u u u m m n x	d e j j j A l y z z z	20+7 20+10 16+7 16+8 17+9 17+7 17+9 22+9 22+10 12+10 20+8	n	z	22	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z
16	i i o w u u u m m z	d e j j j A l l y y	20+7 20+10 16+7 16+8 17+9 17+7 17+9 6+22 22+9 22+7	o	j	23	. N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j
17	i i j j j u u m m	d e e f A A l l y	20+7 20+10 23+5 23+6 23+10 17+7 17+9 22+6 22+9	u	A	24	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A
18	i i j j A A A u m m z	d e e f f B l l l y y	20+7 20+10 23+5 23+6 24+10 24+6 24+5 17+9 22+6 22+9 22+7	u	l	26	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l
19	i i j j A A l l m z	d e e f f B h y y y	20+7 20+10 23+5 23+6 24+10 24+6 26+8 26+8 22+9 22+7	i	d	27	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d
20	d d i j j A A l l m z	s e e e f f B h y y y	27+9 27+5 20+10 23+5 23+6 24+10 24+6 26+8 26+8 22+9 22+7	j	e	28	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e
21	d e e j A A l l m z	s s b f f B h y y y	27+9 28+8 28+6 23+6 24+10 24+6 26+8 26+8 22+9 22+7	j	f	29	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f
22	d e e f A l l m z	s s b b B h y y y	27+9 28+8 28+6 29+8 24+6 26+8 26+8 22+9 22+7	z	y	29	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f, y

23	d e e f A l y	s s b b B h k	27+9 28+8 28+6 29+8 24+6 26+8 29+6	A	B	30	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f, y, B
24	B B l y f e e d	h b h k b b s s	30+6 30+8 26+8 29+6 29+8 28+6 28+8 27+9	e	b	34	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f, y, B, b
25	b B l y	s h h k	34+14 30+6 26+8 29+6	l	h	35	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f, y, B, b, h
26	h y b e d	k k s s s	35+5 29+6 34+14 28+8 27+9	y	k	35	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f, y, B, b, h, k
27	b e d	s s s	48 36 36	e	s	36	N, k, g, r , t, c, p, n, o, w, u, x, i, m, z, j, A, l, d, e, f, y, B, b, h, k, s

ZESTAWIENIE NAJKRÓTSZYCH POŁĄCZEŃ BAZY N Z POZOSTAŁYMI WĘZŁAMI

LP	WĘZEŁ		KOSZTA
	POPRZEDNI	DOCELOWY	DOJAZDU
1	N	N	0
2	N	K	5
3	N	g	6
4	N	r	8
5	N	t	10
6	N	c	11
7	K	p	11
8	g	n	12
9	p	o	16
10	r	w	16
11	n	u	17
12	c	x	20
13	p	i	20
14	n	m	22
15	n	z	22
16	o	j	23
17	u	A	24
18	u	l	26
19	i	d	27
20	j	e	28
21	j	f	28
22	z	y	29
23	A	B	30
24	e	b	34
25	l	h	35
26	y	k	35
27	e	s	36

CZĘŚĆ DRUGA

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

	ETYKIETY PRÓBNE			ETYKIETY TRWAŁE			ZEST.WĘZŁÓW
KROK	WĘZEŁ		CZAS	WĘZEŁ		CZAS	O ETYKIETACH
	POPRZEDNI	NASTĘPNY	DOJAZDU	POPRZEDNI	NASTĘPNY	DOJAZDU	TRWAŁYCH
1	B B	B POZOST.	0 ∞	B	B	0	B
2	B B B	b h A	6 7 6	B	A	6	B, A
3	A A A A	f j u l	6+10 6+10 6+7 6+5	A	l	11	B, A, l
4	l l l	y m u	11+8 11+6 11+9	l	m	17	B, A, l, m
5	m m m	u n z	5+17 17+11 17+10	m	u	22	B, A, l, m, u
6	u u u	n j w	22+5 22+9 22+10	u	n	27	B, A, l, m, u, n
7	n n n n	g r w x	27+6 27+12 27+6 27+15	n	g	33	B, A, l, m, u, n, g
8	g g g	t N r	33+13 33+6 33+9	g	N	39	B, A, l, m, u, n, g, N
9	N N	r K	39+8 39+5	N	K	44	B, A, l, m, u, n, g, N, K

ZESTAWIENIE NAJKRÓTSZEGO POŁACZENIE BAZY N Z WĘZŁEM K

LP	WĘZEŁ		KOSZTA
	POPRZEDNI	DOCELOWY	DOJAZDU
1	B	B	0
2	B	A	6
3	A	l	11
4	l	m	17
5	m	u	22
6	u	n	27
7	n	g	33
8	g	N	39
9	N	K	44

Rysunek drzewa najkrótszych połączeń bazy N z pozostałymi węzłami.

Rysunek najkrótszego połączenia bazy N z węzłem K

Politechnika Wrocławska

Instytut Inżynierii Lądowej

Zakład Budowy Dróg i Lotnisk

Ćwiczenie nr IV

„Drzewo najkrótszych połączeń”

Justyna Kleczewska

Rok:IV

Budowa Dróg i Lotnisk Rok akademicki : 2005/2006

---