Поиск оптимального маршрута по таблице

Поиск оптимального маршрута по таблице

Учитель информатики

Хирьянова В.А.

МОУ «Ропшинская школа»

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F

(при условии, что передвигаться можно только по построенным дорогам).

• полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
• чаще всего используется взвешенный граф , где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки

B

2

A

4

C

7

B

E

2

A

1

4

C

7

E

B

2

4

A

1

4

C

D

3

7

E

B

2

4

A

3

1

4

C

D

3

7

E

B

2

2

4

A

F

3

1

4

C

D

3

7

B

E

2

2

4

F

A

3

1

4

C

D

3

• таким образом, остается найти оптимальный маршрут из A в F
• попробуем перечислить возможные маршруты из А в F:
• А – В – Е – F длина 11
• А – В – С – Е – F длина 9
• А – В – C – D – Е – F длина 11
• А –C – Е – F длина 10
• А –C – B – Е – F длина 14
• А –C – D – Е – F длина 12

• Ответ: А – В – С – Е – F длина 9