Кратчайший путь в графе

Важность использования файлов cookie для корректной работы в интернете 🍪

Формальные описания реальных объектов и процессов

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Найдем все варианты маршрутов из A в E и выберем самый короткий:

• A—B—D—E: длина маршрута 7 км.
• A—B—C—E: длина маршрута 6 км.
• A—B—E: длина маршрута 6 км.

Правильный ответ указан под номером 2.

Другие сценарии

В других сценариях, между пунктами А, В, С, D, Е могут быть следующие длины маршрутов:

Например, для этой ситуации:

• A—B—C—D—E: длина маршрута 13 км.
• A—C—B—D—E: длина маршрута 9 км.
• A—B—D—E: длина маршрута 10 км.
• A—C—D—E: длина маршрута 10 км.

Правильный ответ указан под номером 3.

Заключение

Понимание длин маршрутов между населёнными пунктами очень важно для планирования путешествий или перевозок. Использование информации о протяжённости дорог помогает оптимизировать маршруты и экономить время и ресурсы.

Обратите внимание: данная информация предназначена исключительно в учебных целях и не является практическим руководством.

## Задание 3 № 223
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

- A—D—B—C—E: длина маршрута 12 км.
- A—B—D—C—E: длина маршрута 8 км.

## Задание 3 № 243
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

- A—B—D—E: длина маршрута 9 км.

## Задание 3 № 263
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

- A—B—C—E: длина маршрута 5 км.
- A—C—E: длина маршрута 7 км.

## Задание 3 № 283
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

(Таблица не приведена)

## Задание 3 № 303
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

- A—B—C—D—E: длина маршрута 18 км.
- A—B—E: длина маршрута 12 км.
- A—C—D—E: длина маршрута 13 км.
- А—С—В—Е: длина маршрута 11 км.

## Задание 3 № 323
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:


Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Из пункта A можно попасть в пункты B, C, F.
Из пункта D можно попасть в пункт F.
Из пункта E можно попасть в пункт F.

- A—F: длина маршрута 15 км.
- A—B—C—E—F: длина маршрута 15 км.
- A—B—C—D—F: длина маршрута 14 км.
- A—C—E—F: длина маршрута 14 км.
- A—C—D—F: длина маршрута 13 км.

## Задание 3 № 344
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Из пункта A можно попасть в пункты B, C, D, E.
Из пункта C можно попасть в пункты D, F.

- A—E—F: длина маршрута 7 км.
- A—B—C—F: длина маршрута 8 км.
- A—C—D—E—F: длина маршрута 14 км.
- A—D—E—F: длина маршрута 9 км.
- A—C—F: длина маршрута 5 км.

## Задание 3 № 364
Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице:

Найдём все варианты маршрутов из A в F и выберем самый короткий.

- A-B-C-D-E-F: длина маршрута 18 км.
- A-B-C-F: длина маршрута 9 км.
- A-C-D-E-F: длина маршрута 15 км.
- A-C-F: длина маршрута 6 км.
- A-D-C-F: длина маршрута 7 км.
- A-D-E-F: длина маршрута 10 км.
- A-E-D-C-F: длина маршрута 8 км.
- A-E-F: длина маршрута 7 км.

Кратчайший маршрут имеет длину 6 км.

## Задание 3 № 384
Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице:

Из пункта C можно попасть в пункт F.
Из пункта D можно попасть в пункты E, F.

- A—C—F: длина маршрута 6 км.
- A—D—E—F: длина маршрута 6 км.
- A—D—F: длина маршрута 7 км.

Решение задач № 404

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

• A—B—C—F: длина маршрута 9 км.
• A—C—F: длина маршрута 7 км.
• A—D—E—F: длина маршрута 7 км.

Решение задачи № 424

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

• Из пункта B можно попасть в пункты C, D, F.
• A—C—E—F: длина маршрута 7 км.
• A—F: длина маршрута 9 км.
• A—B—C—E—F: длина маршрута 6 км.
• A—B—F: длина маршрута 7 км.

Решение задачи № 444

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

• A—C—E—F: длина маршрута 8 км.
• A—F: длина маршрута 7 км.
• A—B—C—E—F: длина маршрута 7 км.

Решение задачи № 464

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

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

• Из пункта A можно попасть в пункты B, C, D, E, F.
• A—B—C—D—E—F: длина маршрута 12 км.
• A—C—D—E—F: длина маршрута 5 км.
• A—D—E—F: длина маршрута 4 км.
• A—E—F: длина маршрута 6 км.
• A—F: длина маршрута 5 км.

Правильный ответ указан под номером 4.

Решение задачи № 484

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

• A—B—C—D—E—F: длина маршрута 14 км.
• A—C—D—E—F: длина маршрута 7 км.

Решение задачи № 504

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

• Из пункта A можно попасть в пункты C, D.
• Из пункта B можно попасть в пункты C, F.
• A—C—B—F: длина маршрута 6 км.
• A—D—F: длина маршрута 5 км.

Решение задачи № 524

Между населёнными пунктами A, B, C, D, E, F построены дороги следующей протяжённости:

• A—C—F: длина маршрута 8 км.

Решение задачи № 544

Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Найдём все варианты маршрутов из И в М и выберем самый короткий.

Из пункта И можно попасть в пункты А, Б, Г, М.
Из пункта Г можно попасть в пункты И, М.
Из пункта В можно попасть в пункты А, Б.
Из пункта Б можно попасть в пункты В, И, М.

• И—А—В—Б—М: длина маршрута 7 км.
• И—Б—М: длина маршрута 4 км.
• И—Г—М: длина маршрута 7 км.
• И—М: длина маршрута 8 км.

Самый короткий путь: И—Б—М; Длина маршрута 4 км, самый длинный участок этого пути равен 3.

Задание 3 № 564

Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Ивана-Царевича до Марьи Царевны (от точки И до точки М).

Самый короткий путь: И—Б—М; Длина маршрута 4 км, самый короткий участок этого пути равен 1.

Задание 3 № 584

У Пети Иванова родственники живут в 5 разных городах России. Расстояния между городами внесены в таблицу. Петя перерисовал её в блокнот в виде графа. Считая, что мальчик не ошибся при копировании, укажите, какой граф у Пети в тетради.

1. Не соответствует таблице, поскольку согласно графу не существует прямой дороги из пункта A в пункт D.
2. Не соответствует таблице, поскольку согласно графу расстояние между пунктами D и B равно 3.
3. Граф соответствует таблице.
4. Не соответствует таблице, поскольку согласно графу не существует прямой дороги из пункта D в пункт C.

Задание 3 № 604

У Кати Евтушенко родственники живут в 5 разных городах России. Расстояния между городами внесены в таблицу. Катя перерисовала её в блокнот в виде графа. Считая, что девочка не ошиблась при копировании, укажите, какой граф у Кати в тетради.

1. Не соответствует таблице, поскольку согласно графу не существует прямой дороги из пункта C в пункт E.
2. Граф соответствует таблице.
3. Не соответствует таблице, поскольку согласно графу не существует прямой дороги из пункта D в пункт B.
4. Не соответствует таблице, поскольку согласно графу не существует прямой дороги из пункта B в пункт E.

Задание 3 № 624

Учитель Иван Петрович живёт на станции Антоновка, а работает на станции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Антоновка до станции Дружба.

Найдём все варианты маршрутов из Антоновки в Дружбу и выберем самый короткий.

Задание 3 № 644

Учительница Марья Петровна живёт на станции Васильки, а работает на станции Дружба. Чтобы успеть с утра на уроки, она должна ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Васильки до станции Дружба.

Найдём все ва­ри­ан­ты марш­ру­тов от стан­ции Ва­силь­ки до стан­ции Друж­ба и вы­бе­рем самый ко­рот­кий.

Из пунк­та B можно по­пасть в пункт Сель­ская(С).

Из пунк­та С можно по­пасть в пунк­ты Д, Е.

В—А—Е—Д: длина марш­ру­та 9 км.

В—А—Е—С—Д: длина марш­ру­та 6 км.

В—С—Д: длина марш­ру­та 8 км.

34. За­да­ние 3 № 664. Сель­ская ма­ло­ком­плект­ная школа на­хо­дит­ся в по­сел­ке Ива­нов­ское. Коля Ива­нов живёт в де­рев­не Верш­ки. Опре­де­ли­те, какое ми­ни­маль­ное рас­сто­я­ние ему надо прой­ти, чтобы до­брать­ся до школы:

Найдём все ва­ри­ан­ты марш­ру­тов от де­рев­ни Верш­ки до по­сел­ка Ива­нов­ское и вы­бе­рем самый ко­рот­кий.

Из пунк­та Верш­ки(В) можно по­пасть в пунк­ты Борки(Б), Даль­нее(Да) и Ду­бо­во(Ду).

Из пунк­та Б можно по­пасть в пунк­ты Крас­ное(К), Да, Ива­нов­ское(И).

Из пунк­та К можно по­пасть в пунк­ты Ду, И.

Из пунк­та Да можно по­пасть в пункт И.

В—Б—К—И: длина марш­ру­та 16 км.

В—Б—Да—И: длина марш­ру­та 20 км.

В—Б—И: длина марш­ру­та 14 км.

В—Да—И: длина марш­ру­та 9 км.

В—Ду—К—И: длина марш­ру­та 6 км.

35. За­да­ние 3 № 684. Сель­ская ма­ло­ком­плект­ная школа на­хо­дит­ся в по­сел­ке Верш­ки. Петя Орлов живёт в де­рев­не Даль­нее. Опре­де­ли­те, какое ми­ни­маль­ное рас­сто­я­ние ему надо прой­ти, чтобы до­брать­ся до школы:

Найдём все ва­ри­ан­ты марш­ру­тов от де­рев­ни Даль­нее до по­сел­ка Верш­ки и вы­бе­рем самый ко­рот­кий.

Из пунк­та Даль­нее(Да) можно по­пасть в пунк­ты Борки(Б), Крас­ное(К), Ду­бо­во(Ду) и Ива­нов­ское(И).

Из пунк­та Крас­ное(К) можно по­пасть в пунк­ты Б, Ду, И .

Из пунк­та Верш­ки(В) можно по­пасть в пунк­ты Б, Ду.

Из пунк­та Б можно по­пасть в пункт И.

Да—Б—В: длина марш­ру­та 15 км.

Да—Б—К—Ду—В: длина марш­ру­та 21 км.

Да—К—Ду—В: длина марш­ру­та 8 км.

Да—Ду—В: длина марш­ру­та 9 км.

Да—И—Б—В: длина марш­ру­та 19 км.

Да—И—Б—К—Ду—В: длина марш­ру­та 17 км.

36. За­да­ние 3 № 704. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых(в ки­ло­мет­рах) при­ве­дена в таб­ли­це.

37. За­да­ние 3 № 747. Во­ди­тель ав­то­мо­би­ля дол­жен до­брать­ся из пунк­та А в пункт D за 5 часов. Из пред­став­лен­ных таб­лиц вы­бе­ри­те такую, со­глас­но ко­то­рой во­ди­тель смо­жет до­е­хать из пунк­та А в пункт D за это время. В ячей­ках таб­ли­цы ука­за­но время (в часах), ко­то­рое за­ни­ма­ет до­ро­га из од­но­го пунк­та в дру­гой. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, ука­зан­ным в таб­ли­цах.

Найдём крат­чай­шие марш­ру­ты из A в D для каж­дой таб­ли­цы.

Ис­хо­дя из пер­вой таб­ли­цы, крат­чай­ший марш­рут из A в D: A—C—B—D, его можно пре­одо­леть за 6 часов. Крат­чай­ший марш­рут из A в D для вто­рой таб­ли­цы: A—B—D, его можно пре­одо­леть за 5 часов. Для тре­тьей таб­ли­цы крат­чай­шая до­ро­га: A—C—B—D, она за­ни­ма­ет 6 часов. Для четвёртой таб­ли­цы крат­чай­ший марш­рут: A—D, его можно пре­одо­леть за 6 часов.

38. За­да­ние 3 № 767. Во­ди­тель ав­то­мо­би­ля дол­жен до­брать­ся из пунк­та А в пункт C за 6 часов. Из пред­став­лен­ных таб­лиц вы­бе­ри­те такую, со­глас­но ко­то­рой во­ди­тель смо­жет до­е­хать из пунк­та А в пункт C за это время. В ячей­ках таб­ли­цы ука­за­но время (в часах), ко­то­рое за­ни­ма­ет до­ро­га из од­но­го пунк­та в дру­гой. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, ука­зан­ным в таб­ли­цах.

Найдём крат­чай­шие марш­ру­ты из A в С для каж­дой таб­ли­цы.

Ис­хо­дя из пер­вой таб­ли­цы, крат­чай­ший марш­рут из A в С: A—C, его можно пре­одо­леть за 7 часов. Крат­чай­ший марш­рут из A в С для вто­рой таб­ли­цы: A—B—С, за­ни­ма­ет 7 часов. Для тре­тьей таб­ли­цы крат­чай­шая до­ро­га: A—B—C, она за­ни­ма­ет 7 часов. Для четвёртой таб­ли­цы крат­чай­ший марш­рут: A—B—C, его можно пре­одо­леть за 6 часов.

39. За­да­ние 3 № 799. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и B. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, про­тяжённость ко­то­рых ука­за­на в таб­ли­це.

Ис­кать сле­ду­ет марш­рут, длина ко­то­ро­го не пре­вы­ша­ет 12 км, по­сколь­ку длина A—B со­став­ля­ет 12 км. Рас­смот­рим марш­ру­ты:

A—C—B: длина марш­ру­та 10 км,

A—D—B: длина марш­ру­та 6 км,

A—E—B: длина марш­ру­та 6 км,

A—C—D—B: длина марш­ру­та 4 км.

40. За­да­ние 3 № 819. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Ис­кать сле­ду­ет марш­рут, длина ко­то­ро­го не пре­вы­ша­ет 5 км, по­сколь­ку длина A—B со­став­ля­ет 5 км. Рас­смот­рим марш­ру­ты:

A—C—E—B: длина марш­ру­та 3 км,

A—D—B: длина марш­ру­та 7 км,

A—D—E—B: длина марш­ру­та 5 км.

41. За­да­ние 3 № 841. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

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

Найдём все ва­ри­ан­ты марш­ру­тов из A в B и вы­бе­рем самый ко­рот­кий.

A—C—D—B: длина марш­ру­та 13 км.

A—C—E—B: длина марш­ру­та 12 км.

A—D—C—E—B: длина марш­ру­та 15 км.

A—D—B: длина марш­ру­та 14 км.

42. За­да­ние 3 № 861. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

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

Найдём все ва­ри­ан­ты марш­ру­тов из A в C и вы­бе­рем самый ко­рот­кий.

A—B—D—E—C: длина марш­ру­та 14 км.

A—B—D—C: длина марш­ру­та 7 км.

A—B—E—C: длина марш­ру­та 6 км.

A—D—C: длина марш­ру­та 9 км.

43. За­да­ние 3 № 882. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и D. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, про­тяжённость ко­то­рых ука­за­на в таб­ли­це.

Найдём все ва­ри­ан­ты марш­ру­тов из A в D и вы­бе­рем самый ко­рот­кий.

A—B—C—D: длина марш­ру­та 9 км.

A—D: длина марш­ру­та 8 км.

A—E—D: длина марш­ру­та 6 км.

44. За­да­ние 3 № 902. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и E. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, про­тяжённость ко­то­рых ука­за­на в таб­ли­це.

A—B—D—E: длина марш­ру­та 12 км.

A—D—E: длина марш­ру­та 16 км.

45. За­да­ние 3 № 922. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми A и C. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, про­тяжённость ко­то­рых ука­за­на в таб­ли­це.

Найдём все ва­ри­ан­ты марш­ру­тов из A в С и вы­бе­рем самый ко­рот­кий.

A—B—C: длина марш­ру­та 9 км.

A—C: длина марш­ру­та 8 км.

A—D—C: длина марш­ру­та 12 км.

A—D—E—C: длина марш­ру­та 5 км.

46. За­да­ние 3 № 942. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в км) при­ве­де­на в таб­ли­це.

A—C: длина марш­ру­та 9 км.

A—D—C: длина марш­ру­та 8 км.

A—D—E—C: длина марш­ру­та 7 км.

47. За­да­ние 3 № 1014. Ма­ши­нист элек­тро­по­ез­да дол­жен до­брать­ся из пунк­та А в пункт C за 6 часов. Из пред­став­лен­ных таб­лиц вы­бе­ри­те такую, со­глас­но ко­то­рой ма­ши­нист смо­жет до­е­хать из пунк­та А в пункт C за это время. В ячей­ках таб­ли­цы ука­за­но время (в часах), ко­то­рое за­ни­ма­ет до­ро­га из од­но­го пунк­та в дру­гой. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, ука­зан­ным в таб­ли­цах.

Ис­хо­дя из пер­вой таб­ли­цы, крат­чай­ший марш­рут из A в С: A—B—C, его можно пре­одо­леть за 8 часов. Для вто­рой таб­ли­цы крат­чай­шая до­ро­га: A—B—C, она за­ни­ма­ет 6 часов.й­ший марш­рут: A—B—C, его можно пре­одо­леть за 7 часов.

48. За­да­ние 3 № 1034. Ма­ши­нист элек­тро­по­ез­да дол­жен до­брать­ся из пунк­та А в пункт C за 4 часа. Из пред­став­лен­ных таб­лиц вы­бе­ри­те такую, со­глас­но ко­то­рой ма­ши­нист смо­жет до­е­хать из пунк­та А в пункт C за это время. В ячей­ках таб­ли­цы ука­за­но время (в часах), ко­то­рое за­ни­ма­ет до­ро­га из од­но­го пунк­та в дру­гой. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, ука­зан­ным в таб­ли­цах.

Ис­хо­дя из пер­вой таб­ли­цы, крат­чай­ший марш­рут из A в С: A—B—C, его можно пре­одо­леть за 7 часов. Крат­чай­ший марш­рут из A в С для вто­рой таб­ли­цы: A—D—С, за­ни­ма­ет 8 часов. Для тре­тьей таб­ли­цы крат­чай­шая до­ро­га: A—D—С, она за­ни­ма­ет 7 часов. Для четвёртой таб­ли­цы крат­чай­ший марш­рут: A—B—D—С, его можно пре­одо­леть за 4 часа.

49. За­да­ние 3 № 1054. В таб­ли­це при­ве­де­на сто­и­мость пе­ре­во­зок между пятью же­лез­но­до­рож­ны­ми стан­ци­я­ми, обо­зна­чен­ны­ми бук­ва­ми A, B, C, D и E. Ука­жи­те схему, со­от­вет­ству­ю­щую таб­ли­це.

Из таб­ли­цы видно, что из пунк­та A есть до­ро­ги в любой дру­гой пункт. Сле­до­ва­тель­но, под­хо­дит толь­ко ва­ри­ант 2.

50. За­да­ние 3 № 1074. В таб­ли­це при­ве­де­на сто­и­мость пе­ре­во­зок между пятью же­лез­но­до­рож­ны­ми стан­ци­я­ми, обо­зна­чен­ны­ми бук­ва­ми A, B, C, D и E. Ука­жи­те схему, со­от­вет­ству­ю­щую таб­ли­це.

Из таб­ли­цы видно, что из пунк­та A есть до­ро­ги толь­ко в пунк­ты B и C. Сле­до­ва­тель­но, под­хо­дят толь­ко ва­ри­анты 3 и 4. Рас­сто­я­ние между пунк­та­ми A и C — 1, таким об­ра­зом, под­хо­дит толь­ко ва­ри­ант 4.

51. За­да­ние 3 № 1097. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

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

Из пунк­та A можно до­брать­ся в пунк­ты B, C и D. Про­ана­ли­зи­ру­ем не­ко­то­рые воз­мож­ные марш­ру­ты.

Марш­рут A — B — D, длина 7 км.

Марш­рут A — С — D, длина 6 км.

Марш­рут A — E — С — D явно длин­нее марш­ру­та A — С — D.

Любые дру­гие марш­ру­ты будут длин­нее марш­ру­та A — С — D. Таким об­ра­зом, крат­чай­шее рас­сто­я­ние между пунк­та­ми A и D со­став­ля­ет 6 км.

52. За­да­ние 3 № 1117. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

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

Из пунк­та B можно до­брать­ся в пунк­т C. Про­ана­ли­зи­ру­ем не­ко­то­рые воз­мож­ные марш­ру­ты.

Марш­рут B — C — E, длина 8 км.

Марш­рут B — С — A — E, длина 10 км.

Марш­рут B — A — С — D — E, длина 6 км.

Любые дру­гие марш­ру­ты будут длин­нее марш­ру­та B — A — С — D — E. Таким об­ра­зом, крат­чай­шее рас­сто­я­ние между пунк­та­ми B и E со­став­ля­ет 6 км.

53. За­да­ние 3 № 1137. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Марш­рут A — B — D, длина 9 км.

Марш­рут A — С — D, длина 8 км.

Марш­рут A — D, длина 10 км.

Любые дру­гие марш­ру­ты будут длин­нее марш­ру­та A — С — D. Таким об­ра­зом, крат­чай­шее рас­сто­я­ние между пунк­та­ми A и D со­став­ля­ет 8 км.

54. За­да­ние 3 № 1157. Между населёнными пунк­та­ми A, B, C, D по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Марш­рут A — B — C, длина 7 км.

Марш­рут A — D — C, длина 6 км.

Марш­рут A — B — D — C, длина 5 км.

Любые дру­гие марш­ру­ты будут длин­нее марш­ру­та A — B — D — C. Таким об­ра­зом, крат­чай­шее рас­сто­я­ние между пунк­та­ми A и C со­став­ля­ет 5 км.

55. За­да­ние 3 № 1216. Между населёнными пунк­та­ми A, B, C, D по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Из пунк­та B можно по­пасть в пунк­т D.

Из пунк­та C можно по­пасть в пунк­ты E, F.

Из пунк­та E можно по­пасть в пунк­ты F, D.

Из пунк­та F можно по­пасть в пункт D.

A — B — D: длина марш­ру­та 11 км.

A — C — E — F — D: длина марш­ру­та 13 км.

A — C — E — D: длина марш­ру­та 8 км.

A — C — F — D: длина марш­ру­та 9 км.

56. За­да­ние 3 № 1256. Между населёнными пунк­та­ми A, B, C, D, E по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це.

Опре­де­ли­те длину крат­чай­ше­го пути между пунк­та­ми B и E. Пе­ре­дви­гать­ся можно толь­ко по до­ро­гам, про­тяжённость ко­то­рых ука­за­на в таб­ли­це.

"Кратчайший путь в графе"

Кратчайший путь в графе

Крылов С.С., Чуркина Т.Е. Информатика основной государственный экзамен. Москва: Издательство "Национальное образование", 2023. — 144 с. Материалы публикуются в учебных целях

Между населёнными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами А и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.

Выпишем все пути из А в E, проходящие через пункт С:

Наименьшая длина равна 34.

На экзамене это задание принесло бы тебе 2/2 баллов.

Удалить курс из корзины?

Этот курс можно приобрести только с помощью менеджера или преподавателя. Уверен, что хочешь удалить его из корзины?

Введите больше 6 символов

Зарегистрируйся и Демо мастер-группы на по любимым предметам .

Как тебя зовут?

Введите не меньше 2 символов

Привяжем номер телефона

Теперь нужно подтвердить номер – введи код из СМС

Почти закончили! Теперь нужно создать надежный пароль

Немного о тебе

В какой класс ты переходишь?

Укажи, какие предметы будешь или хочешь сдавать

Пополнение счёта

К сожалению, данный курс заблокирован. Необходимо внести доплату

Этот урок не входит в

Можешь приобрести полный курс, чтобы получить доступ ко всему содержимому.

Тебе стали доступны демо-курсы. Смотри вебы, делай домашки – следующие 10 дней у тебя безграничный доступ. Курсы доступны в разделе “Мое обучение”.

Вывод средств

Ваше задание подтверждено!

Теперь вы можете приступить к следующему уроку курса по математике

Подтверждение замены

Для смены номера телефона мы отправили Вам код по СМС, введите его в поле ниже.

Ты включаешь автопродление – 25-го числа каждого месяца доступ к купленным курсам будет автоматически продлеваться. Деньги будут списываться с одной из привязанных к учетной записи банковских карт. Управлять автопродлением можно из раздела "Финансы"

Для активации регулярного платежа мы спишем небольшую сумму с карты и сразу её вернем

Вы дествительно хотите отменить автопродление?

Благодарим за покупку!

В ближайшее время курс будет доступен в разделе Моё обучение

Материалы будут доступны за сутки до начала урока

Чат будет доступен после выдачи домашнего задания

Укажите вашу электронную почту