1 of 113

Взвешенные графы. Поиск кратчайшего пути. Динамическое программирование на ориентированных ациклических графах. Подсчет числа путей.

Дианкин Игорь

2 of 113

Виды графов

Ориентированный

Неориентированный

2

1

2

1

2

3 of 113

Виды графов

Ориентированный

Неориентированный

3

1

2

1

2

4 of 113

Виды графов

Цикличный

Ацикличный

4

B

A

C

1

0

2

3

5 of 113

Виды графов

Цикличный

Ацикличный

5

B

A

C

1

0

2

3

6 of 113

Взвешенные графы

Невзвешенный

Взвешенный

6

1

0

3

2

1

0

3

2

1

2

3

4

7 of 113

Взвешенные графы. Топологическая сортировка

Граф должен быть ациклическим и ориентированным. Может быть как взвешенным, так и невзвешенным.

7

A

B

C

D

E

F

G

1

8 of 113

Взвешенные графы. Топологическая сортировка

8

A

B

C

D

E

F

G

1

СВЯЗНЫЙ СПИСОК

1

9 of 113

Взвешенные графы. Топологическая сортировка

9

A

B

C

D

E

F

G

1

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

10 of 113

Взвешенные графы. Топологическая сортировка

10

A

B

C

D

E

F

G

1

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

11 of 113

Взвешенные графы. Топологическая сортировка

11

A

B

C

D

E

F

G

1

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

12 of 113

Взвешенные графы. Топологическая сортировка

12

A

B

C

D

E

F

G

1

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

13 of 113

Взвешенные графы. Топологическая сортировка

13

A

B

C

D

E

F

G

1

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

14 of 113

Взвешенные графы. Топологическая сортировка

14

A

B

C

D

E

F

G

1

G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

15 of 113

Взвешенные графы. Топологическая сортировка

15

A

B

C

D

E

F

G

1

F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

16 of 113

Взвешенные графы. Топологическая сортировка

16

A

B

C

D

E

F

G

1

F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

17 of 113

Взвешенные графы. Топологическая сортировка

17

A

B

C

D

E

F

G

1

E
F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

18 of 113

Взвешенные графы. Топологическая сортировка

18

A

B

C

D

E

F

G

1

D
E
F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

19 of 113

Взвешенные графы. Топологическая сортировка

19

A

B

C

D

E

F

G

1

C
D
E
F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

20 of 113

Взвешенные графы. Топологическая сортировка

20

A

B

C

D

E

F

G

1

C
D
E
F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

21 of 113

Взвешенные графы. Топологическая сортировка

21

A

B

C

D

E

F

G

1

B
C
D
E
F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

1

22 of 113

Взвешенные графы. Топологическая сортировка

22

A

B

C

D

E

F

G

1

A
B
C
D
E
F
G

СВЯЗНЫЙ СПИСОК

ПОИСК В ГЛУБИНУ

23 of 113

Взвешенные графы. Топологическая сортировка

23

A
B
C
D
E
F
G

СВЯЗНЫЙ СПИСОК

A

B

C

D

E

F

G

A

B

C

D

E

F

G

1

24 of 113

Поиск кратчайшего пути

Поиск кратчайшего пути применяется к взвешенным и не взвешенным графам.

Если мы хотим найти путь из вершины S в вершину T графе, мы подразумеваем путь по ребрам графа такой, что сумма весов пройденных ребер будет наименьшей. Если весов нет, то количество ребер.

Например в данном графе есть два пути из S в T, S-A-T (суммарный вес 1 + 3 = 4) и S-B-T (суммарный вес 2 + 4 = 6). Кратчайшим путем будет S-A-T.

24

A

S

T

B

1

2

3

4

25 of 113

Поиск кратчайшего пути. Поиск в ширину.

Ищем путь из 0 в 6.

Граф невзвешенный

Граф может быть неориентированным

25

0

2

3

4

5

6

26 of 113

Поиск кратчайшего пути. Поиск в ширину.

26

0

2

3

4

5

Ищем путь из 0 в 6

6

27 of 113

Поиск кратчайшего пути. Поиск в ширину.

27

Ищем путь из 0 в 6

0

2

3

4

5

6

28 of 113

Поиск кратчайшего пути. Поиск в ширину.

28

Ищем путь из 0 в 6

0

2

3

4

5

6

0

29 of 113

Поиск кратчайшего пути. Поиск в ширину.

29

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

30 of 113

Поиск кратчайшего пути. Поиск в ширину.

30

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

31 of 113

Поиск кратчайшего пути. Поиск в ширину.

31

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

32 of 113

Поиск кратчайшего пути. Поиск в ширину.

32

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

33 of 113

Поиск кратчайшего пути. Поиск в ширину.

33

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

34 of 113

Поиск кратчайшего пути. Поиск в ширину.

34

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

35 of 113

Поиск кратчайшего пути. Поиск в ширину.

35

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

36 of 113

Поиск кратчайшего пути. Поиск в ширину.

36

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

37 of 113

Поиск кратчайшего пути. Поиск в ширину.

37

Ищем путь из 0 в 6

0

2

3

4

5

6

0

2

3

4

0-2-4-6

38 of 113

Динамическое программирование на ациклических ориентированных графах

Имеет те же ограничения, что и топологическая сортировка, так как использует ее.

Базируется на идее, что любой подпуть в кратчайшем пути также является кратчайшим.

38

A

B

C

D

E

39 of 113

Динамическое программирование

39

B

A

C

D

E

F

G

J

H

I

1

3

2

4

2

1

2

3

2

1

40 of 113

Динамическое программирование

40

B

A

C

D

E

F

G

J

H

I

1

3

2

4

2

1

2

3

2

1

ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА

41 of 113

ЗАДАНИЕ. Топологически отсортировать граф

41

B

A

C

D

E

F

G

J

H

I

1

3

2

4

2

1

2

3

2

1

42 of 113

ЗАДАНИЕ. Топологически отсортировать граф

42

B

A

C

D

E

F

G

J

H

I

1

3

2

4

2

1

2

3

2

1

B

A

C

D

E

F

G

J

H

I

2

3

2

1

2

4

1

3

1

43 of 113

Динамическое программирование

43

B

A

C

D

E

F

G

J

H

I

2

3

2

1

2

4

1

3

1

PATH	A	B	C	D	E	F	G	H	I	J
WEIGHT	∞	0	0	0	0	0	0	0	0	0

44 of 113

Динамическое программирование

44

B

A

C

D

E

F

G

J

H

I

2

3

2

1

2

4

1

3

1

PATH	A	B	C	D	E	F	G	H	I	J
WEIGHT	∞	0	0	0	0	0	0	0	0	0

45 of 113

Динамическое программирование

45

2

3

2

1

2

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D	E	F	G	H	I	J
WEIGHT	0	0	0	0	0	0	0	0	0	0

WEIGHT(D)

=

MIN

WEIGHT(A) + 2

46 of 113

Динамическое программирование

46

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D	E	F	G	H	I	J
WEIGHT	0	0	0	0	0	0	0	0	0	0

WEIGHT(B)

=

MIN

0 + 2

2

47 of 113

Динамическое программирование

47

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D(A)	E	F	G	H	I	J
WEIGHT	0	0	0	2	0	0	0	0	0	0

WEIGHT(B)

=

MIN

2

48 of 113

Динамическое программирование

48

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D(A)	E	F	G	H	I	J
WEIGHT	0	0	0	2	0	0	0	0	0	0

WEIGHT(G)

=

MIN

WEIGHT(D) + 3

2

49 of 113

Динамическое программирование

49

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D(A)	E	F	G	H	I	J
WEIGHT	0	0	0	2	0	0	0	0	0	0

WEIGHT(G)

=

MIN

2 + 3

2

50 of 113

Динамическое программирование

50

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	0	0	2	0	0	5	0	0	0

WEIGHT(G)

=

MIN

5

2

51 of 113

Динамическое программирование

51

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	0	0	2	0	0	5	0	0	0

WEIGHT(C)

=

MIN

WEIGHT(A) + 3

2

52 of 113

Динамическое программирование

52

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	0	0	2	0	0	5	0	0	0

WEIGHT(C)

=

MIN

0 + 3

2

53 of 113

Динамическое программирование

53

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	0	3	2	0	0	5	0	0	0

WEIGHT(C)

=

MIN

3

2

54 of 113

Динамическое программирование

54

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	0	3	2	0	0	5	0	0	0

WEIGHT(B)

=

MIN

WEIGHT(A) + 1

2

55 of 113

Динамическое программирование

55

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	0	3	2	0	0	5	0	0	0

WEIGHT(B)

=

MIN

0 + 1

2

56 of 113

Динамическое программирование

56

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B(A)	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	1	3	2	0	0	5	0	0	0

WEIGHT(B)

=

MIN

0 + 1

2

57 of 113

Динамическое программирование

57

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B(A)	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	1	3	2	0	0	5	0	0	0

WEIGHT(F)

=

MIN

WEIGHT(B) + 2

2

58 of 113

Динамическое программирование

58

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B(A)	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	1	3	2	0	0	5	0	0	0

WEIGHT(F)

=

MIN

WEIGHT(B) + 2

WEIGHT(C) + 1

2

59 of 113

Динамическое программирование

59

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B(A)	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	1	3	2	0	0	5	0	0	0

WEIGHT(F)

=

MIN

WEIGHT(B) + 2

WEIGHT(C) + 1

WEIGHT(D) + 1

2

60 of 113

Динамическое программирование

60

2

3

2

1

2

4

1

3

1

B

A

C

D

E

F

G

J

H

I

PATH	A	B(A)	C(A)	D(A)	E	F	G(D)	H	I	J
WEIGHT	0	1	3	2	0	0	5	0	0	0

WEIGHT(F)

=

MIN

1 + 2

3 + 1

2 + 2

61 of 113

Динамическое программирование

61

WEIGHT(F)

=

MIN

3

4

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I	J
WEIGHT	0	1	3	2	0	3	5	0	0	0

62 of 113

Динамическое программирование

62

WEIGHT(I)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I	J
WEIGHT	0	1	3	2	0	3	5	0	0	0

WEIGHT(F) + 2

63 of 113

Динамическое программирование

63

WEIGHT(I)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I	J
WEIGHT	0	1	3	2	0	3	5	0	0	0

WEIGHT(F) + 2

WEIGHT(G) + 1

64 of 113

Динамическое программирование

64

WEIGHT(I)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I	J
WEIGHT	0	1	3	2	0	3	5	0	0	0

3 + 2

5 + 1

65 of 113

Динамическое программирование

65

WEIGHT(I)

=

MIN

5

6

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	0	3	5	0	5	0

1

66 of 113

Динамическое программирование

66

WEIGHT(E)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	0	3	5	0	5	0

WEIGHT(B) + 4

1

67 of 113

Динамическое программирование

67

WEIGHT(E)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	0	3	5	0	5	0

1 + 4

1

68 of 113

Динамическое программирование

68

WEIGHT(E)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	5	3	5	0	5	0

5

1

69 of 113

Динамическое программирование

69

WEIGHT(H)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	5	3	5	0	5	0

1

WEIGHT(E) + 1

70 of 113

Динамическое программирование

70

WEIGHT(H)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	5	3	5	0	5	0

1

WEIGHT(E) + 1

WEIGHT(F) + 1

71 of 113

Динамическое программирование

71

WEIGHT(H)

=

MIN

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H	I(F)	J
WEIGHT	0	1	3	2	5	3	5	0	5	0

1

5 + 1

3 + 1

72 of 113

Динамическое программирование

72

WEIGHT(H)

=

MIN

6

4

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H(F)	I(F)	J
WEIGHT	0	1	3	2	5	3	5	4	5	0

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

1

73 of 113

Динамическое программирование

73

WEIGHT(J)

=

MIN

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H(F)	I(F)	J
WEIGHT	0	1	3	2	5	3	5	4	5	0

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

1

WEIGHT(H) + 1

74 of 113

Динамическое программирование

74

WEIGHT(J)

=

MIN

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H(F)	I(F)	J
WEIGHT	0	1	3	2	5	3	5	4	5	0

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

1

WEIGHT(H) + 1

WEIGHT(I) + 1

75 of 113

Динамическое программирование

75

WEIGHT(J)

=

MIN

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H(F)	I(F)	J
WEIGHT	0	1	3	2	5	3	5	4	5	0

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

1

4 + 1

5 + 1

76 of 113

Динамическое программирование

76

WEIGHT(J)

=

MIN

PATH	A	B(A)	C(A)	D(A)	E(B)	F(B)	G(D)	H(F)	I(F)	J(H)
WEIGHT	0	1	3	2	5	3	5	4	5	5

2

3

2

1

4

1

3

1

B

A

C

D

E

F

G

J

H

I

2

1

5

6

77 of 113

Динамическое программирование. Задание.

77

A

B

C

D

E

ПУТЬ ИЗ А В Е

3

1

PATH	A	B	C	D	E
WEIGHT	∞	0	0	0	0

78 of 113

Подсчет числа путей. Динамическое программирование

78

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

ГРАФ - АЦИКЛИЧЕСКИЙ

79 of 113

Подсчет числа путей

79

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(T) = count(E) + count(F)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

80 of 113

Подсчет числа путей

80

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(T) = count(E) + count(F)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

81 of 113

Подсчет числа путей

81

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(E) = count(A) + count(B)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

82 of 113

Подсчет числа путей

82

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(E) = count(A) + count(B)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

83 of 113

Подсчет числа путей

83

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(A) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

84 of 113

Подсчет числа путей

84

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	FALSE
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(A) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

85 of 113

Подсчет числа путей

85

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(A) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

86 of 113

Подсчет числа путей

86

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(A) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

87 of 113

Подсчет числа путей

87

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(E) = count(A) + count(B)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

88 of 113

Подсчет числа путей

88

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(E) = count(A) + count(B)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

89 of 113

Подсчет числа путей

89

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(B) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

90 of 113

Подсчет числа путей

90

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	FALSE
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(B) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

91 of 113

Подсчет числа путей

91

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	FALSE
F	FALSE
T	FALSE

count(B) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

92 of 113

Подсчет числа путей

92

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(E) = count(A) + count(B)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

93 of 113

Подсчет числа путей

93

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(T) = count(E) + count(F)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

94 of 113

Подсчет числа путей

94

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

95 of 113

Подсчет числа путей

95

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

96 of 113

Подсчет числа путей

96

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

97 of 113

Подсчет числа путей

97

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	FALSE
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(C) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

98 of 113

Подсчет числа путей

98

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(C) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

99 of 113

Подсчет числа путей

99

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

100 of 113

Подсчет числа путей

100

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

101 of 113

Подсчет числа путей

101

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(D) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

102 of 113

Подсчет числа путей

102

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	FALSE
E	TRUE	2
F	FALSE
T	FALSE

count(D) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

103 of 113

Подсчет числа путей

103

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	FALSE
T	FALSE

count(D) = count(S)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

104 of 113

Подсчет числа путей

104

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

105 of 113

Подсчет числа путей

105

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

106 of 113

Подсчет числа путей

106

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

107 of 113

Подсчет числа путей

107

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	FALSE
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

108 of 113

Подсчет числа путей

108

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	TRUE	4
T	FALSE

count(F) = count(E) + count(C) + count(D)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

109 of 113

Подсчет числа путей

109

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	TRUE	4
T	FALSE

count(T) = count(E) + count(F)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

110 of 113

Подсчет числа путей

110

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	TRUE	4
T	FALSE

count(T) = count(E) + count(F)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

111 of 113

Подсчет числа путей

111

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	TRUE	4
T	TRUE	6

count(T) = count(E) + count(F)

S

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

112 of 113

Подсчет числа путей

112

S

B

A

C

D

E

F

T

V	COUNTED	COUNT
S	TRUE	1
A	TRUE	1
B	TRUE	1
C	TRUE	1
D	TRUE	1
E	TRUE	2
F	TRUE	4
T	TRUE	6

СЧИТАЕМ ПУТИ ИЗ S В T РЕКУРСИВНО

count(T) = count(E) + count(F)

113 of 113

Время работы алгоритмов.

Обход в ширину

Топологическая сортировка

O(E + V)

Динамическое программирование

O(E + V)

Подсчет числа путей

O(E + V)

113