Модель транспортной сети представляет собой чертеж-схему на плане местности с указанием вершин (пунктов) транспортной сети. Ее построение производится по заданной схеме расположения пунктов, по наличию звеньев сети, соединяющих два соседних пункта, и длине этих звеньев. В нашем курсовом проекте мы использовали готовую схему транспортной сети, которая приведена в приложении А.
Для решения задачи отыскания кратчайших расстояний между пунктами транспортной сети применяется метод потенциалов, как наиболее удобный. В этом случае задача решается по алгоритму, состоящему из двух шагов.
Шаг I. Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал Vi = 0.
Шаг 2. Просматриваются все звенья, начальные пункты i которых имеют потенциал Vi, а для конечных j потенциалы не присвоены. Затем определяются значения потенциалов конечных пунктов j по следующей формуле:
(1.1)
где Vj(i) - потенциал конечного пункта j звена i-j;
lij – длина звена i-j, т.е. расстояние между пунктами i и j.
Из всех полученных потенциалов выбирается потенциал c наименьшим значением, т.е. определяется
;
, (1.2)
где {Vj(i)} - множество значений потенциалов конечных пунктов j звеньев i-j, i-м начальным пунктом которых ранее присвоены потенциалы;
{Vj’(i’)} - потенциал конечного пункта j’ звена i’-j’, являвшийся наименьшим по значению элементом множества {Vj(i)}.
Потенциал {Vj’(i’)} присваивается соответствующему конечному пункту j’, а звено i’-j’ отмечается звездочкой.
В случае если несколько значений потенциалов множества {Vj(i)} окажутся равными и наименьшими, то необходимо установить, относятся они к одному и тому же пункту или нет. Когда наименьшие равные значения потенциалов относятся к paзличным конечным пунктам j’, то эти значения потенциалов присваивается всем соответствующим конечным пунктам j’ и отмечаются звездочками соответствующие значения i’-j’. Если наименьшие равные значения потенциалов относятся к одному и тому же конечному пункту j’, то пункту j’ присваивается это наименьшее значение потенциала и отмечается звездочкой то звено i’-j’, которому соответствует потенциал Vj’(i’) с большим удельным весом в его составе длин звеньев с лучшими дорожными условиями (при одинаковых дорожных условиях отмечается стрелкой любое из звеньев 
).
Шаг 2 повторяется до тех пор, пока всем вершинам заданной сети не будут присвоены потенциалы.
Ниже приведен пример расчета для пунктов А1, А2 транспортной сети, для удобства значения заносятся в таблицу (см. таблицы 1.1 и 1.2 ).
Таблица 1.1 – Расчет кратчайших расстояний для пункта А1
|
№ шага |
Пункты транспортной сети | |||||||||
|
А1 |
А2 |
А3 |
А4 |
А5 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 | |
|
1 |
(0,+∞)* |
(А1,11) |
(А1,4) |
(А1,+∞) |
(А1,10) |
(А1,9) |
(А1,18) |
(А1,19) |
(А1,6) |
(А1,17) |
|
2 |
(А1,11) |
(А1,4)* |
(А1,+∞) |
(А1,10) |
(А1,9) |
(А3,9) |
(А1,19) |
(А1,6) |
(А1,17) | |
|
3 |
(А1,11) |
(А1,+∞) |
(А1,10) |
(А1,9) |
(А3,9) |
(А1,19) |
(А1,6)* |
(А1,17) | ||
|
4 |
(А1,11) |
(Б1,21) |
(А1,10) |
(А1,9)* |
(А3,9) |
(А1,19) |
(А1,17) | |||
|
5 |
(А1,11) |
(Б1,21) |
(А1,10) |
(А3,9)* |
(А1,19) |
(А1,17) | ||||
|
6 |
(А1,11) |
(Б1,21) |
(А1,10)* |
(А1,19) |
(А1,17) | |||||
|
7 |
(А1,11)* |
(Б1,21) |
(А2,16) |
(А1,17) | ||||||
|
8 |
(Б1,21) |
(А2,16)* |
(А1,17) | |||||||
|
9 |
(Б1,21) |
(А1,17)* | ||||||||
|
10 |
(Б1,21)* | |||||||||