М

Хорошо, давай разберёмся с задачей. Нам нужно найти кратчайший путь в графе из вершины A в вершину D.

Чтобы это сделать, давай посчитаем длину каждого возможного пути и выберем самый короткий. Длина пути – это сумма весов рёбер, соединяющих вершины на этом пути.

Смотрим на граф и видим, что пути из A в D могут идти через разные вершины. Возможные пути:

1. A-C-D: длина пути равна 2+3=5
2. A-C-E-D: длина пути равна 2+1+1=4
3. A-E-D: длина пути равна 4+1=5
4. A-N-E-D: длина пути равна 1+2+1=4
5. A-N-B-D: длина пути равна 1+3+2=6
6. A-N-B-E-D: длина пути равна 1+3+1+1=6

Из всех вариантов самый короткий путь – это путь A-C-E-D или путь A-N-E-D, оба имеют длину в 4 единицы. То есть ответ, который нужно ввести, – это число 4.

Вот так вот, сосед по парте, мы нашли ответ. Пиши смело 4 в окошке ответа!