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

Задание 4: В Задании 4 по информатике дана таблица дорог между населёнными пунктами A, B, C, D и E; требуется найти длину кратчайшего маршрута между A и D с учётом.

ОГЭ информатикаЗадание №4Короткий ответКратчайший путьВзвешенный граф по таблице

Задание

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

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

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

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

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

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

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

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

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

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

Нужно рассмотреть заданную таблицу весов дорог между населенными пунктами A, B, C, D и E. Таблица задаёт взвешенный граф, где каждое не пустое значение обозначает длину дороги между двумя пунктами. В задаче путь между A и D должен проходить по дорогам без повторения вершин, то есть граф используется без циклов. Навык здесь — построение эвристики поиска пути в взвешенном графе и аккуратное чтение матрицы смежности: определить, какие пары вершин связаны дорогами и с каким весом. При подходе к решению полезно выписать доступные ребра и их веса, затем перебрать варианты последовательностей посещения вершин, чтобы найти минимальную суммарную длину пути A–D, не заходя в повторение вершин. Такой подход формирует базовые навыки анализа графов, умение работать с таблицами смежности и вычислять кратчайшие маршруты.