Пътища, построени между населени места A, B, C, D, E, F

Формулиране на задачата: Изградени са пътища между населени места A, B, C, D, E, F, чиято дължина е дадена в таблицата. (Липсата на число в таблицата означава, че между точките няма пряк път.) Определете дължината на най-краткия път между точки A и F (при условие, че можете да се движите само по изградените пътища).

Задачата е включена в изпита по информатика за клас 11 под номер 3 (Анализ на информационни модели).

Нека разгледаме как се решават подобни задачи, като използваме пример.

Изградени са пътища между населени места A, B, C, D, E, F, чиято дължина е показана в таблицата. (Липсата на число в таблицата означава, че няма пряк път между точките.)

места

Определете дължината на най-краткия път между точки A и F (при условие, че можете да се движите само по изградените пътища).

Помислете за всички възможни маршрути, по които можете да стигнете от точка А до точка F:

можете стигнете

От точка A има само 1 път до точка B. От точка B можете да стигнете до точки A, C, D и E, но точка A трябва да бъде изключена, тъй като вече сме били там.

От точка C можете да стигнете само до точка E (изключваме B). От точка E можете да стигнете до точки D и F (изключваме B и C). Точка D също трябва да бъде изключена, тъй като от нея можете да стигнете само до точки В и Е, където вече сме били. Дължината на маршрута A - B - C - E - F е:

От точка D можете да стигнете до точка E (изключваме B). От точка E можете да стигнете до точки C и F (изключваме B и D). Точка С също трябва да бъде изключена, тъй като от нея можете да стигнете само до точки В и Е, където вече сме били. Дължината на маршрута A - B - D - E - F е:

От точка E можете да стигнете само до точки C, D и F (изключваме B). Точки C и D също трябва да бъдат изключени, тъй като от тях можете да стигнете само до точки B и E, където вече сме били. Дължината на маршрута A - B - E - F е:

От 3-те маршрута най-краткият е A - B - D - E - F, дължината му е 14. По този начин верният отговор е 3.

Споделете статията със съучениците си "Пътища между населени места A, B, C, D, E, F - как да се реши".

Има и друг начин за решаване?

Предложете друг начин за решаване на проблема „Изградени са пътища между населени места A, B, C, D, E, F“. Може би ще бъде по-разбираемо за някого: