3. ОПРЕДЕЛЕНИЕ ПОТЕНЦИАЛОВ УЗЛОВ ПРИ ПОМОЩИ АЛГОРИТМА ДИЙКСТРЫ
Потенциал узла-источника берем равным π1=0, потенциал остальных узлов присваиваем значение R, где R – бесконечно большое число. Узел 1 заносим в список начальных узлов ( далее СНУ).
Таблица 2 – Список начальных узлов (СНУ)
Номер итерации
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Начальный узел
1
4
2
8
5
6
11
7
9
13
14
12
10
3
2.1 Перерасчётпотенциалов узлов, соседних с узлом-источником:
π2=π1+h1,2=0+55=55
π2=55; π4=34; π5=999.
(π4< π2< π5) →выбираем узел 4 и заносим его в СНУ.
2.2 Начальный узел 4:
π8=π4+h4,8=34+40=74
3.2 Не все узлы вСНУ. Выбираем начальный узел для третьей итерации:
π2=55; π8=74; π5=89.
(π2< π8< π5) →выбираем узел 4 и заносим его в СНУ.
2.3 Начальный узел 2:
π5=π2+h2,5=55+32=87<89, π5=[87];
π3=π2+h2,3=55+122=177
π8=74; π3=177; π5=87
(π8< π5< π3) →выбираем узел 8 и заносим его в СНУ.
2.4 Начальный узел 8:π12=π8+h8,12=74+86=160
π9=127; π3=177; π5=87; π12=160;
(π5< π9< π12<π3) →выбираем узел 5 и заносим его в СНУ.
2.5 Начальный узел 5:
π9=π5+h5,9=87+58=145
π9=127; π3=177; π12=160; π11=289; π6=109
(π6< π9< π12<π3<π11) →выбираем узел 6 и заносим его в СНУ.
2.6 Начальный узел 6:
π7=π6+h6,7=109+18=127
3.6 Не все узлы включены в СНУ. Выбираем начальный узел для седьмой итерации:
π9=127; π3=177; π12=160; π11=121; π7=127
(π11< π7≤π9< π12<π3) →выбираем узел 11 и заносим егов СНУ.
2.7 Начальный узел 11:
π13=π11+h11,13=121+54=175
π9=127; π3=177; π12=160; π13=175; π7=127; π14=159; π15=1120;
(π7≤π9<π14< π12<π13<π3<π15) →выбираем узел 7 и заносим его в СНУ.
2.8 Начальный узел 7:π10=π7+h7,10=127+42=169
π9=127; π3=177; π12=160; π13=175; π14=159; π15=1120; π10=169;
(π9<π14< π12<π10<π13<π3<π15) →выбираем узел 9 и заносим его в СНУ.
2.9 Начальный узел 9:
π11=π9+h9,11=127+32=159>121, π11=[121];
π12=π9+h9,12=127+46=173>160 , π12=[160];
π13=π9+h9,13=127+24=151<175 , π13=[151];
3.9 Не все узлывключены в СНУ. Выбираем начальный узел для десятой итерации:
π3=177; π12=160; π13=151; π14=159; π15=1120; π10=169;
(π13< π14<π12<π10<π3<π15) →выбираем узел 13 и заносим его в СНУ.
2.10 Начальный узел 13:
π14=π13+h13,14=151+25=176>159 , π14=[159];
3.10 Не все узлы включены в СНУ. Выбираем начальный узел для одиннадцатой итерации:
π3=177; π12=160; π14=159; π15=1120; π10=169;
(π14<π12<π10<π3<π15)→выбираем узел 14 и заносим его в СНУ.
2.11 Начальный узел 14
π15=π14+h14,15=159+34=193<1120 , π15=[193];
3.11 Не все узлы включены в СНУ. Выбираем начальный узел для двенадцатой итерации:
π3=177; π12=160; π15=193; π10=169;
(π12<π10<π3<π15) →выбираем узел 12 и заносим его в СНУ.
2.12 Начальный узел 12:
π13=π12+h12,13=160+33=193>151, π13=[153];
3.12 Не все узлы включены в СНУ. Выбираем начальный узелдля тринадцатой итерации:
π3=177; π10=169; π15=193
(π10<π3<π15) →выбираем узел 10 и заносим его в СНУ.
2.13 Начальный узел 10:
π15=π10+h10,15=169+75=244>193, π15=[193];
π11=π10+h10,11=169+23=192>121, π13=[121];
3.12 Не все узлы включены в СНУ. Выбираем начальный узел для четырнадцатой итерации:
Выбираем узел 3 и заносим его в сну, т.к. узел 6 уже вошел в СНУи...
Потенциал узла-источника берем равным π1=0, потенциал остальных узлов присваиваем значение R, где R – бесконечно большое число. Узел 1 заносим в список начальных узлов ( далее СНУ).
Таблица 2 – Список начальных узлов (СНУ)
Номер итерации
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Начальный узел
1
4
2
8
5
6
11
7
9
13
14
12
10
3
2.1 Перерасчётпотенциалов узлов, соседних с узлом-источником:
π2=π1+h1,2=0+55=55
π2=55; π4=34; π5=999.
(π4< π2< π5) →выбираем узел 4 и заносим его в СНУ.
2.2 Начальный узел 4:
π8=π4+h4,8=34+40=74
3.2 Не все узлы вСНУ. Выбираем начальный узел для третьей итерации:
π2=55; π8=74; π5=89.
(π2< π8< π5) →выбираем узел 4 и заносим его в СНУ.
2.3 Начальный узел 2:
π5=π2+h2,5=55+32=87<89, π5=[87];
π3=π2+h2,3=55+122=177
π8=74; π3=177; π5=87
(π8< π5< π3) →выбираем узел 8 и заносим его в СНУ.
2.4 Начальный узел 8:π12=π8+h8,12=74+86=160
π9=127; π3=177; π5=87; π12=160;
(π5< π9< π12<π3) →выбираем узел 5 и заносим его в СНУ.
2.5 Начальный узел 5:
π9=π5+h5,9=87+58=145
π9=127; π3=177; π12=160; π11=289; π6=109
(π6< π9< π12<π3<π11) →выбираем узел 6 и заносим его в СНУ.
2.6 Начальный узел 6:
π7=π6+h6,7=109+18=127
3.6 Не все узлы включены в СНУ. Выбираем начальный узел для седьмой итерации:
π9=127; π3=177; π12=160; π11=121; π7=127
(π11< π7≤π9< π12<π3) →выбираем узел 11 и заносим егов СНУ.
2.7 Начальный узел 11:
π13=π11+h11,13=121+54=175
π9=127; π3=177; π12=160; π13=175; π7=127; π14=159; π15=1120;
(π7≤π9<π14< π12<π13<π3<π15) →выбираем узел 7 и заносим его в СНУ.
2.8 Начальный узел 7:π10=π7+h7,10=127+42=169
π9=127; π3=177; π12=160; π13=175; π14=159; π15=1120; π10=169;
(π9<π14< π12<π10<π13<π3<π15) →выбираем узел 9 и заносим его в СНУ.
2.9 Начальный узел 9:
π11=π9+h9,11=127+32=159>121, π11=[121];
π12=π9+h9,12=127+46=173>160 , π12=[160];
π13=π9+h9,13=127+24=151<175 , π13=[151];
3.9 Не все узлывключены в СНУ. Выбираем начальный узел для десятой итерации:
π3=177; π12=160; π13=151; π14=159; π15=1120; π10=169;
(π13< π14<π12<π10<π3<π15) →выбираем узел 13 и заносим его в СНУ.
2.10 Начальный узел 13:
π14=π13+h13,14=151+25=176>159 , π14=[159];
3.10 Не все узлы включены в СНУ. Выбираем начальный узел для одиннадцатой итерации:
π3=177; π12=160; π14=159; π15=1120; π10=169;
(π14<π12<π10<π3<π15)→выбираем узел 14 и заносим его в СНУ.
2.11 Начальный узел 14
π15=π14+h14,15=159+34=193<1120 , π15=[193];
3.11 Не все узлы включены в СНУ. Выбираем начальный узел для двенадцатой итерации:
π3=177; π12=160; π15=193; π10=169;
(π12<π10<π3<π15) →выбираем узел 12 и заносим его в СНУ.
2.12 Начальный узел 12:
π13=π12+h12,13=160+33=193>151, π13=[153];
3.12 Не все узлы включены в СНУ. Выбираем начальный узелдля тринадцатой итерации:
π3=177; π10=169; π15=193
(π10<π3<π15) →выбираем узел 10 и заносим его в СНУ.
2.13 Начальный узел 10:
π15=π10+h10,15=169+75=244>193, π15=[193];
π11=π10+h10,11=169+23=192>121, π13=[121];
3.12 Не все узлы включены в СНУ. Выбираем начальный узел для четырнадцатой итерации:
Выбираем узел 3 и заносим его в сну, т.к. узел 6 уже вошел в СНУи...
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат