Перейти к содержанию

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

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

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

1)4 2)5 3)6 4)7


Для решения этой задачи воспользуемся специальным алгоритмом, который эффективно решает именно такого вида задачу — находит кратчайшее расстояние на графе от одной вершины до другой. Этот алгоритм называется алгоритмом Дейкстры. Побочным эффектом алгоритма Дейкстры является нахождение кратчайшего расстояния от некоей стартовой вершины до всех остальных вершин графа. Но это никоим образом не ухудшает его качества — алгоритм Дейкстры ищет кратчайшее расстояние быстро, надежно и эффективно.

16-17. Среди всех листовых вершин будем искать одинаковые вершины. Сейчас таких пар нет.

Среди листовых вершин найдём вершину с наименьшим расстоянием. В данном случае это вершина E. Вычеркнем эту вершину из списка доступных вершин. Это конечная вершина, расстояние до которой мы искали. Алгоритм закончен.

Кратчайшее расстояние — 5.

Ответ: 5