2 Решение задачи

Разработка схемы автобусных маршрутов состоит из нескольких этапов.

2.1 Этап 1. Определение (по времени) путей между пунктами (микрорайонами)

Этот этап выполняется с помощью потенциалов – нахождение кратчайших расстояний. Он состоит из двух шагов.

Шаг 1. Присвоим начальному узлу сети потенциал 0. В данной задаче первым начальным узлом примем пункт 1. Присвоим ему потенциал 0 (рис. 2).

Шаг 2. Просмотрим все звенья, начальные узлы которых имеют потенциалы, а конечные нет. Определим потенциалы конечных узлов как соединяющему начальный и конечный узлы. Выберем конечный узел с наименьшим потенциалом, запишем его рядом с узлом и отметим звено стрелкой. Шаг 2 повторяем до тех пор, пока всем узлам не будут присвоены потенциалы.

Рисунок 2 - Определение кратчайших путей

Звенья со стрелочками показывают кратчайший путь от пункта 1 ко всем остальным пунктам. Результаты этих расчетов записываем в табл. 3, где в соответствующих клетках в верхнем левом углу указаны пункты между начальным и конечным пунктами.

Аналогично выполняются расчеты по всем пунктам, каждый из которых последовательно принимается за начальный, а результаты вносятся в табл. 3, где выявлены все кратчайшие по времени следования маршруты между всеми пунктами транспортной сети.

Таблица 3 – Кратчайшие (по времени) маршруты между всеми пунктами сети

Откуда	Куда
№ микрорайона	13	14	9	1	3	10	5	12
13				5,9	9	9	9
		51	36	99	125	64	74	100
14				9,5			9
	51		41	102	93	31	70	64
9				5				10
	36	41		62	89	31	37	85
1	5,9	9,5	5		11	5,9
	99	102	62		63	93	25	107
3	9
	125	93	89	63		70	85	82
10	9			5,9			9
	64	31	31	93	70		68	49
5	9	9				9		9,10
	74	70	37	25	85	68		121
12			10				9,10
	100	64	85	107	82	49	121