Нахождение оптимального маршрута

Задача состоит в отыскании кратчайшего расстояния в транспортных сетях, представленных ранее. Рассматриваемые транспортные сети являются ацикличными, т.е. не содержат циклов.

Представляем найденные расстояния в табличной форме для каждой сети.

В соответствии с формулой (2.1) определяем потенциалы и находим для каждого узла сети.

U_j = min{U_i + d_ij} (2.1)

где d_ij – расстояния между связными узлами i и j;

U_j – кратчайшее расстояние между узлами 1 и j.

Сеть 1.

	-
		-
			-
				-
					-
						-
							-
								-

U₁ = 0

U₂ = min{U₁ + d₁₂} = {0+102} = 102 (из узла 1)

U₃ = min{U₁ + d₁₃} = {0+47} = 47 (из узла 1)

U₄ = min{U₂ + d₂₄; U₃ + d₃₄ }= min{102+60; 47+113}=160(из узла 3)

U₅ = min{U₂ + d₂₅; U₃ + d₃₅} = min{102+62; 47+58} = 105 (из узла 3)

U₆ = min{U₄ + d₄₆; U₅ + d₅₆} = min{160+90; 105+209} =250 (из узла 4)

U₇ = min{U₄ + d₄₇; U₅ + d₅₇}= min{160+157; 105+79}=184 (из узла 5)

U₈ = min{U₆ + d_68; U₇ + d₇₈} = min{250+30; 184+174} =280 (из узла 6)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Уманью и Ильичевском;

- построить оптимальный маршрут следования.

Итак, минимальное расстояние составляет 280 км.

Сеть 2.

	-
		-
			-
				-
					-
						-
							-
								-

U₁ = 0

U₂ = min{U₁ + d₁₂} = {0+49} = 49 (из узла 1)

U₃ = min{U₁ + d₁₃} = {0+95} = 95 (из узла 1)

U₄ = min{U₂ + d₂₄; U₃ + d₃₄ }= min{49+184; 95+181}=233 (из узла 2)

U₅ = min{U₂ + d₂₅; U₃ + d₃₅} = min{49+122; 95+134} =171 (из узла 2)

U₆ = min{U₄ + d₄₆; U₅ + d₅₆} = min{233+180; 171+260} =413 (из узла 4)

U₇ = min{U₄ + d₄₇; U₅ + d₅₇}= min{233+201; 171+303}=434 (из узла 4)

U₈ = min{U₆ + d_68; U₇ + d₇₈} = min{413+179; 434+180} =592 (из узла 6)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Волоховым Яром и Ейском;

- построить оптимальный маршрут следования.

Итак, минимальное расстояние составляет 592 км.

Сеть 3.

	-
		-
			-
				-
					-
						-
							-
								-

U₁ = 0

U₂ = min{U₁ + d₁₂} = {0+220} = 220 (из узла 1)

U₃ = min{U₁ + d₁₃} = {0+280} = 280 (из узла 1)

U₄ = min{U₂ + d₂₄; U₃ + d₃₄ }= min{220+209; 280+169}=429(из узла 2)

U₅ = min{U₂ + d₂₅; U₃ + d₃₅} = min{220+315; 280+274} = 535 (из узла 2)

U₆ = min{U₄ + d₄₆; U₅ + d₅₆} = min{429+168; 535+118} =597 (из узла 4)

U₇ = min{U₄ + d₄₇; U₅ + d₅₇}= min{429+209; 535+124}=638 (из узла 4)

U₈ = min{U₆ + d_68; U₇ + d₇₈} = min{597+134;638+123} =731 (из узла 6)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Бахмачом и Ильичевском;

- построить оптимальный маршрут следования.

Итак, минимальное расстояние составляет 731 км.

Сеть 4.

	-
		-
			-
				-
					-
						-
							-
								-

U₁ = 0

U₂ = min{U₁ + d₁₂} = {0+45} = 45 (из узла 1)

U₃ = min{U₁ + d₁₃} = {0+116} = 116 (из узла 1)

U₄ = min{U₂ + d₂₄; U₃ + d₃₄ }= min{45+188; 116+108}=233(из узла 2)

U₅ = min{U₂ + d₂₅; U₃ + d₃₅} = min{45+149; 116+180} = 194 (из узла 2)

U₆ = min{U₄ + d₄₆; U₅ + d₅₆} = min{233+192; 194+124} = 318 (из узла 5)

U₇ = min{U₄ + d₄₇; U₅ + d₅₇}= min{233+107; 194+59}=253 (из узла 5)

U₈ = min{U₆ + d_68; U₇ + d₇₈} = min{318+122;253+224} =440 (из узла 6)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Сочи и Ейском;

- построить оптимальный маршрут следования.

Итак, минимальное расстояние составляет 440 км.