Длина кратчайшего пути между пунктами (только таблица) —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#49351

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


	$A$	$B$	$C$	$D$	$E$	$F$	$G$

$A$		2		6

$B$	2		5	3

$C$		5		1			8

$D$	6	3	1		9	7

$E$				9			5

$F$				7			7

$G$			8		5	7

Определите длину кратчайшего пути между пунктами $A$ и $G$ . Передвигаться можно только по указанным дорогам.

Показать ответ и решение

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут:

$A − B − D − C − G$ . Его длина равна $2+ 3+ 1 +8 = 14$ .

Стоит отметить, что изменение маршрута приведет к увеличению количества слагаемых и их сумме.

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 2#5451

Между населёнными пунктами 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 (при условии, что передвигаться можно только по построенным дорогам).

Показать ответ и решение

Для удобства представим таблицу в виде графа.

$PIC$

Начнем из пункта А. Из него мы можем попасть в 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.

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 3#6449

Между населёнными пунктами 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 (при условии, что передвигаться можно только по построенным дорогам).

Показать ответ и решение

Для удобства представим таблицу в виде графа:

$PIC$

Т.к. в пункт 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.

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 4#50660

Между населёнными пунктами 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.

$PIC$

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 5#50661

Между населёнными пунктами 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.

$PIC$

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 6#55050

Между населёнными пунктами 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

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 7#55051

Между населёнными пунктами 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 (при условии, что передвигаться можно только по построенным дорогам).

Показать ответ и решение

Найдём и рассмотрим некоторые пути, в которых мы можем из пункта А дойти до пункта В:

$1)A → B$
$2)A → C → B$
$3)A → D → B$
$4)A → F → D → B$

Длина первого пути составит 10 у.е. Второго пути - 2 у.е. Невозможно найти длину меньшую, чем у второго пути, по этой причине ответ для данной задачи равен 2.

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 8#56950

Между населёнными пунктами 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.

Ответ: 27

Ошибка.
Попробуйте повторить позже

Задача 9#62816

МС отправился в путешествие к стобальникам. Прилетев в Омск, ему нужно добраться до очередного села, где живет стобальник. Между населёнными пунктами А, Б, В,Г, Д, Е, Ж построены дороги (если их можно так назвать) с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Направление дороги определяется от строки к столбцу, например, пересечение A и Б означает, что дорога идет от точки A к Б


	А	Б	В	Г	Д	Е	Ж

А		4	7

Б			2	7	8

В					3	4

Г							3

Д							4

Е							5

Ж

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

Показать ответ и решение

Рассмотрим все возможные траектории:

А — Б — Г — Ж = 14

А — Б — Д — Ж = 16

А — Б — В — Д — Ж = 13

А — В — Д — Ж = 14

А — В — Е — Ж = 16

Длина кратчайшего пути — 13

Ответ: 13


	$A$	$B$	$C$	$D$	$E$	$F$	$G$

$A$		2		6

$B$	2		5	3

$C$		5		1			8

$D$	6	3	1		9	7

$E$				9			5

$F$				7			7

$G$			8		5	7


	$A$	$B$	$C$	$D$	$E$	$F$	$G$

$A$		2		6

$B$	2		5	3

$C$		5		1			8

$D$	6	3	1		9	7

$E$				9			5

$F$				7			7

$G$			8		5	7

1.01 Длина кратчайшего пути между пунктами (только таблица)


	$A$	$B$	$C$	$D$	$E$	$F$	$G$

$A$		2		6

$B$	2		5	3

$C$		5		1			8

$D$	6	3	1		9	7

$E$				9			5

$F$				7			7

$G$			8		5	7