Практикум по динамическому программированию. Решение задач, страница 3

3.Транспортная сеть состоит из 10 (m=10) узлов, некоторые из которых соединены магистралями. Стоимость проезда по каждой из таких магистралей известна tij (см. табл. 3). Требуется найти оптимальный маршрут из 1-го пункта в 10-й. Движение только слева направо.

 
 


Таблица 3

t12

t13

t14

t25

t36

t46

t57

t58

t67

t69

t710

t810

t910

1

7

24

12

5

10

9

20

21

7

6

10

24

5

2

8

25

13

6

11

10

21

22

8

7

11

25

6

3

9

26

14

7

12

11

22

23

9

8

12

26

7

4

10

27

5

8

13

12

23

24

10

9

13

27

8

5

11

28

6

9

14

13

24

25

11

10

14

28

9

6

12

29

7

10

5

14

25

26

12

11

5

29

10

7

13

30

8

11

6

15

26

27

13

12

6

30

11

8

14

31

9

12

7

16

27

28

14

13

7

31

12

9

15

32

10

13

8

17

28

29

15

14

8

32

13

10

16

33

11

14

9

18

29

30

16

15

9

33

14

11

17

34

12

15

10

19

30

31

17

16

10

34

15

12

18

35

13

16

11

20

31

32

18

17

11

35

16

13

15

30

16

16

11

20

32

32

18

20

11

34

16

14

15

25

16

16

11

20

32

28

17

20

11

29

16

15

15

25

14

11

11

20

28

28

17

26

11

29

16

16

15

10

14

11

18

20

28

28

17

26

11

17

16

17

7

11

12

9

14

5

28

7

7

8

14

10

9

18

6

12

11

8

13

14

7

8

6

7

13

11

8

19

5

13

10

7

12

13

8

9

5

6

12

12

7

20

14

14

9

6

11

12

9

10

14

5

11

13

6

21

13

15

8

5

10

11

10

11

13

14

10

14

5

22

12

16

7

14

9

10

11

12

12

13

9

15

14

23

11

17

6

13

8

11

12

13

11

12

8

16

13

24

10

18

5

12

7

12

13

14

10

11

7

17

12

25

11

19

14

11

6

13

14

15

11

10

6

18

11

26

12

20

13

10

5

14

15

16

12

11

5

19

10

27

13

21

12

11

14

5

16

17

13

12

14

20

11

28

14

22

11

12

13

6

17

18

14

13

13

21

12

29

5

23

10

13

12

7

18

19

5

14

12

22

13

30

6

24

11

14

11

8

19

20

6

5

11

23

14