Ошибка.
Попробуйте повторить позже
Между населёнными пунктами 
, 
, 
, 
, 
, 
, 
построены дороги, протяжённость которых приведена в
таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
 |  |  |  |  |  |  | |
 | 2 | 6 | |||||
 | 2 | 5 | 3 | ||||
 | 5 | 1 | 8 | ||||
 | 6 | 3 | 1 | 9 | 7 | ||
 | 9 | 5 | |||||
 | 7 | 7 | |||||
 | 8 | 5 | 7 | ||||
Определите длину кратчайшего пути между пунктами 
и 
. Передвигаться можно только по указанным
дорогам.
Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут:
. Его длина равна 
.
Стоит отметить, что изменение маршрута приведет к увеличению количества слагаемых и их сумме.
Ошибка.
Попробуйте повторить позже
МС отправился в путешествие к стобальникам. Прилетев в Омск, ему нужно добраться до очередного села, где живет стобальник. Между населёнными пунктами А, Б, В,Г, Д, Е, Ж построены дороги (если их можно так назвать) с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Направление дороги определяется от строки к столбцу, например, пересечение A и Б означает, что дорога идет от точки A к Б
| А | Б | В | Г | Д | Е | Ж | |
| А | 4 | 7 | |||||
| Б | 2 | 7 | 8 | ||||
| В | 3 | 4 | |||||
| Г | 3 | ||||||
| Д | 4 | ||||||
| Е | 5 | ||||||
| Ж | |||||||
Определите длину кратчайшего пути между пунктами A и Ж (при условии, что передвигаться можно только по построенным дорогам).
Рассмотрим все возможные траектории:
А — Б — Г — Ж = 14
А — Б — Д — Ж = 16
А — Б — В — Д — Ж = 13
А — В — Д — Ж = 14
А — В — Е — Ж = 16
Длина кратчайшего пути — 13
Ошибка.
Попробуйте повторить позже
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего маршрута между пунктами А и В. Передвигаться можно только по указанным дорогам
В ответе укажите одно число - кратчайший путь.
Пункт В единственный имеет 4 дороги, значит, ему соответствует пункт П5. Пункт А единственный имеет 2 дороги, значит, ему соответствует пункт П6. Пункты А и В встречаются в пункте Б, значит пункт Б - П1. Пункт Е имеет 1 дорогу, он является пунктом П3. Тогда пункт Д - П4, а пункт Г - П2. Из пункта А в пункт В можно добраться следующими способами:
A →B, длина этого пути 
A →Б →B, длина этого пути 
A →Б →Г →В, длина этого пути 
A →Б →Г →Д →В, длина этого пути 
Получаем, что наименьшая длина пути равна 13.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
| A | B | C | D | E | F | |
| A | 5 | 7 | 11 | 19 | ||
| B | 5 | 6 | ||||
| C | 7 | 6 | ||||
| D | 11 | 6 | 6 | 8 | 6 | |
| E | 8 | 8 | ||||
| F | 19 | 6 | 8 | |||
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.
Для данной задачи необходимо нарисовать граф и расставить на нем значения длины дорог.
Далее нам необходимо удалить дороги по условию об обязательном пункте E. Так же исключим дороги с пунктом В.
Отсюда получается самый короткий путь A — D — E — F и составляет он 27.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | 10 | 1 | 4 | 6 | ||
| B | 10 | 1 | 6 | |||
| C | 1 | 1 | 7 | |||
| D | 4 | 6 | 8 | |||
| E | 7 | |||||
| F | 6 | 8 | ||||
Определите длину кратчайшего пути между пунктами A и B (при условии, что передвигаться можно только по построенным дорогам).
Найдём и рассмотрим некоторые пути, в которых мы можем из пункта А дойти до пункта В:
Длина первого пути составит 10 у.е. Второго пути - 2 у.е. Невозможно найти длину меньшую, чем у второго пути, по этой причине ответ для данной задачи равен 2.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | 1 | 3 | 9 | 5 | 12 | |
| B | 1 | 1 | ||||
| C | 3 | 6 | 15 | |||
| D | 9 | 6 | 3 | 2 | ||
| E | 5 | 1 | 15 | 3 | 6 | |
| F | 12 | 2 | 6 | |||
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Кратчайший путь: A+B+E+D+F= 7
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | 1 | 4 | 4 | 15 | ||
| B | 1 | 5 | ||||
| C | 4 | 5 | ||||
| D | 4 | 5 | 5 | 2 | 9 | |
| E | 2 | 6 | ||||
| F | 15 | 9 | 6 | |||
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Рисуем схему из дорог между точками по предоставленной таблице. Глядя на таблицу, понимаем, что после D идти в C нет смысла, так как дорога дальше ведёт только в A, с точкой B после D та же ситуация. Также, пропускаем пункты, которые в текущем рассматриваемом нами пути уже были, для получения минимального результата.
Получаем в итоге такую же схему, как в прикреплённом изображении. Считаем длины и выясняем, что кратчайший путь — A -> D -> E -> F, он равен 12.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | |
| A | 2 | 4 | 6 | 19 | ||
| B | 2 | 3 | ||||
| C | 4 | 5 | ||||
| D | 6 | 3 | 5 | 2 | 7 | |
| E | 2 | 6 | ||||
| F | 19 | 7 | 6 | |||
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Рисуем схему из дорог между точками по предоставленной таблице. Глядя на таблицу, понимаем, что после D идти в C нет смысла, так как дорога дальше ведёт только в A, с точкой B после D та же ситуация. Также, пропускаем пункты, которые в текущем рассматриваемом нами пути уже были, для получения минимального результата.
Получаем в итоге такую же схему, как в прикреплённом изображении. Считаем длины и выясняем, что кратчайший путь — A -> B -> D -> F, он равен 12.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.
Для удобства представим таблицу в виде графа:
Прямой путь из A в F = 16. Как видим из графа, через B и C мы можем пройти только в D, тогда определим наименьший путь из A в D: через B – 3 + 5 = 8, C – 4 + 2 = 6, прямой – 4. Итак, в D из A можно добраться путем длины 4.
Из D можно сразу добраться в F путем длины 10,а через E – путем длины 6 + 3 = 9. То есть через D добраться до F можно путем длины 4 + 9 = 13 < 16 (прямой путь из A в F). Значит, 13 – наш ответ.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет
Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам. В ответе укажите только число.
Для удобства представим таблицу в виде графа:
Из вершины A попасть в вершину D можно путем длины 5 (через В): прямой (длина = 6) и через С (длина = 2 + 5 + 1 = 8) больше, поэтому их мы не рассматриваем.
Из вершины D можно попасть в G через F – тогда длина пути = 7 + 7 = 14 – или через E – тогда длина = 9 + 5 = 14. То есть из D мы попадаем в G путем длины 14, тогда минимальный путь через D в G = 5 + 14 = 19.
Из C в G можно попасть за 8 (варианты, когда идем через D, уже рассмотрены выше – мы решили, что через С идти в D дольше, чем через B, поэтому этот вариант мы не рассматриваем). Попасть в С можно за 6: мы можем сделать это маршрутами A-D-C (длина = 6 + 1 = 7), A-B-D-C (длина = 2 + 3 + 1 = 6), A-B-C (длина = 2 + 5 = 7).
Значит, в С из А мы попадаем путем длины 6, а из С в G – 8. То есть из A в G через С – за 6 + 8 = 14 < 19 (путь через D). Значит, 14 – наш ответ.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
| A | B | C | D | E | F | |
| A | 4 | 2 | ||||
| B | 4 | 7 | 1 | |||
| C | 2 | 7 | 3 | 4 | ||
| D | 3 | 3 | ||||
| E | 1 | 4 | 3 | 2 | ||
| F | 2 | |||||
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Для удобства представим таблицу в виде графа:
Т.к. в пункт F можем попасть только из E, сейчас задача сводится к нахождению кратчайшего расстояния между А и Е.
Сейчас нужно аккуратно разобрать все случаи. Итак, если мы идем из А в В, до Е мы можем добраться следующими способами: A-B-E = 4 + 1 = 5, A-B-C-E = 4 + 7 + 4 = 15 – причем из графа видно, что в вершину D заходить не стоит: мы сделаем крюк.
Если мы идем из А в С, то до Е мы доходим так: А-С-Е = 2 + 4 = 6. Видим, что из А до Е наименьшее расстояние по маршруту A-B-E = 5. Тогда A-F = 5 + 2 = 7.
Ошибка.
Попробуйте повторить позже
Между населёнными пунктами A, B, C, D, E, F, G построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
| A | B | C | D | E | F | G | |
| A | 6 | 4 | 21 | ||||
| B | 6 | 1 | |||||
| C | 4 | 1 | 5 | 27 | |||
| D | 5 | 4 | 8 | 10 | |||
| E | 4 | 1 | 8 | ||||
| F | 8 | 1 | 2 | ||||
| G | 21 | 27 | 10 | 8 | 2 | ||
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Для удобства представим таблицу в виде графа.
Начнем из пункта А. Из него мы можем попасть в B, С и сразу в G. Запомним, что A-G = 21. Пункт В приведет только к пункту С. A-B-C = 6 + 1 = 7, A-C = 4. Т.к. в обоих случаях мы попадаем в пункт С, выбираем наиболее короткий путь: это прямой путь A-C = 4.
Из пункта C мы можем попасть в пункт D и в пункт G – нашу цель. До пункта C длина пути 4, из С в G – 27, то есть A-G = 31. Это больше, чем прямой путь, посчитанный ранее, поэтому это значение запоминать не будем.
Значит, идем в пункт D. A-D = A-C + 5 = 9. Из пункта D можем попасть в E, F.
Посмотрим, какой маршрут короче. Из пункта F мы можем попасть в E – и оттуда в G – и сразу в G. D-F-E-G = 8 + 1 + 8 = 17, D-F-G = 8 + 2 = 10. Из пункта E можем пойти в F – и потом в G – или сразу в G: D-E-F-G = 4 + 1 + 2 = 7, D-E-G = 4 + 8 = 12. Выбираем кратчайший маршрут: D-E-F-G = 7.
Итак, A-C = 4, D-E-F-G = 7, то есть A-G = 4 + 5 + 7 (учитываем дорогу C-D) = 16. Прямая дорога A-G = 21, а A-C-D-E-F-G = 16.
Значит, ответ – 16.
