ФИПИ ОГЭ информатика, задание 4 (2E5EA0)

Задание 4: Задача OГЭ по информатике: по таблице дорог между пунктами A, B, C, D, E определить длину кратчайшего пути между A и D, посещая узлы не более одного раза.

ОГЭ информатикаЗадание №4Короткий ответКратчайший путьГрафы и схемы

Задание

№4 · Модели объектов

Впишите правильный ответ.

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

	A	B	C	D	E
A		2	5		6
B	2		2
C	5	2		6	1
D			6		4
E	6		1	4

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

Подсказка AI-репетитора

Подсказки открываются по одной и не показывают готовый ответ.

Показано 0 из 3

Задание 4: кратчайший путь между A и D по таблице дорог

Задание 4: анализ графа дорог между пунктами A, B, C, D, E

Задача строит граф на основе таблицы дорог между пунктами A, B, C, D и E. Нужно найти минимальную совокупную длину пути от A до D, используя только существующие дороги и не посещая узлы дважды. В решении следует учесть пары вершин с данными весами: A–B (2), A–C (5), A–E (6), B–A (2), B–C (2), C–A (5), C–B (2), C–D (6), C–E (1), D–C (6), D–E (4), E–A (6), E–C (1), E–D (4). Это учебный пример для тренировки навыков работы с графами и поиск кратчайшего пути с ограничением посещения узлов один раз; подход строится на анализе вариантов маршрутов и сравнении их длин.