Профильная информатика:
подготовка к ЕГЭ и олимпиадам

1 2 3 4 5 6 7 8 9 10^Р 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Между городами \(v_{1},\ldots,v_{8}\) построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между городами нет.

	\(v_1\)	\(v_2\)	\(v_3\)	\(v_4\)	\(v_5\)	\(v_6\)	\(v_7\)	\(v_8\)
\(v_1\)		4	5		8
\(v_2\)			2	6
\(v_3\)					3	2
\(v_4\)	13					1	5
\(v_5\)						1		9
\(v_6\)							3	6
\(v_7\)								2
\(v_8\)		3	5	6		7	8

Определите длину кратчайшего пути из города \(v_{1}\) до самого дальнего от него города.

Решение

Для решения задачи может использоваться алгоритм Дейкстры.

Подробнее...