Задание №1702/03

Задание

Между городами \(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}\) до самого дальнего от него города.

Решение

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

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

Ответ

12

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

© Д. В. Богданов, 2012–2018.