Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.

Bosh sahifa

Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

6

Hajmi:

1.7 MB

Ko'chirib olish shartlari

Mavzu: Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.
Reja:
1 . Kirish .
2. Asosiy qisim
1. Eng qisqa yo’llar masalalarining turlari.
2. Deykstra algoritmning so’zli tavsifi
3. Masalaning qo’yilishi.
4. Deysktra algoritmi.
3 . Xulosa.
4. Foydalanilgan adabiyotlar.

Kirish
Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi
uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda,
biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-
ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning
ketma-ketligi algoritm deb ataymiz.
Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab
chiqish prinsiplarini o‘rganadigan maxsus “Algoritmlar nazariyasi” bo‘limi xam
mavjud.
Algoritmlar nazariyasi – algoritmlarning umumiy xossalari , qonuniyatlari va
ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan
shug'ullanadi. Algoritm tushunchasini formallashtirish asosida ularning
samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo‘llanilish sohasini
aniqlash mumkin.
Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu
shahargacha sayohat qilishning eng qisqa yo'li nima? Bu yigirma daqiqada
mo'ljallangan eng qisqa yo'l uchun algoritm. Bir kuni ertalab men yosh yigitlar
bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe
terastasiga o'tirdik va men buni qila olamanmi yoki yo'qmi deb o'ylagandim va
keyinchalik eng qisqa yo'l uchun algoritmni yaratdim . Men aytganimdek, yigirma
daqiqalik ixtiro bo'ldi. Darhaqiqat, u 59 yil ichida, uch yil o'tib nashr etildi. Bu
kitob hali ham o'qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi bo'lgan
sabablardan biri men uni qalam va qog'ozsiz tasvirladim. Keyinchalik bilib
oldimki , qalam va qog'ozsiz loyihalashtirishning afzalliklaridan biri deyarli barcha
oldini olish mumkin bo'lgan murakkabliklardan qochishingiz kerak. Oxir-oqibat,
bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan.
- Edzger Dijkstra, ACM bilan aloqa, Philip L. Frana, 2001.
Dijkstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli
yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida eng
qisqa yo'l muammosini o'ylab topdi.Uning maqsadi ham hisoblanmaydigan
odamlar tushunishi mumkin bo'lgan muammoni va echimni (kompyuter tomonidan
ishlab chiqariladigan) tanlash edi. U eng qisqa yo'l algoritmini ishlab chiqdi va
undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan transport
xaritasi uchun ARMAC uchun amalga oshirdi (64, ya'ni 6 bit shahar raqamini
kodlash uchun etarli bo'ladi).Bir yil o'tgach, u institutning navbatdagi
kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch
keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo'lgan simni
kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi deb
nomlanadigan algoritmni (avvalroq Jarnikka ma'lum va shuningdek, Primni qayta

$#include #include // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance array int printSolution(int dist[], int n) { printf("Vertex Distance from Source\n"); for (int i = 0; i < V; i++) printf("%d tt %d\n", i, dist[i]); } // Function that implements Dijkstra's single source shortest path algorithm$ $// for a graph represented using adjacency matrix representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the shortest // distance from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest // path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V-1; count++) { // Pick the minimum distance vertex from the set of vertices not // yet processed. u is always equal to src in the first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is an edge from // u to v, and total weight of path from src to v through u is$ $// smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist, V); } // driver program to test above function int main() { /* Let us create the example graph discussed above */ int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {8, 11, 0, 0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7, 0}$ $}; dijkstra(graph, 0); return 0; } 2-ko’rinish: #include #include /*Used for INT_MAX*/ using namespace std ; #define vertex 7 /*It is the total no of verteices in the graph*/ int minimumDist(int dist[], bool Dset[]) /*A method to find the vertex with minimum distance which is not yet included in Dset*/ { int min=INT_MAX,index; /*initialize min with the maximum possible value as infinity does not exist */ for(int v=0;v<="" p="" style="color: rgb(0, 0, 0); font-family: "Times New Roman"; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font- variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text- align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;"> { if(Dset[v]==false && dist[v]<=min) { min=dist[v]; index=v; }$ $} return index; { int dist[vertex]; bool Dset[vertex]; for(int i=0;i<="" p=""> { dist[i]=INT_MAX; Dset[i]=false; } dist[src]=0; /*Initialize the distance of the source vertec to zero*/ for(int c=0;c<="" p=""> { int u=minimumDist(dist,Dset); /*u is any vertex that is not yet included in Dset and has minimum distance*/ Dset[u]=true; /*If the vertex with minimum distance found include it to Dset*/ for(int v=0;v<="" p=""> /*Update dist[v] if not in Dset and their is a path from src to v through u that has distance minimum than current value of dist[v]*/ { if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u] [v]<dist[v])< p=""> dist[v]=dist[u]+graph[u][v];</dist[v])<>$ $} } cout<<"Vertex\t\tDistance from source"<<="" p=""> for(int i=0;i<="" p=""> { char c=65+i; cout<<c<<"\t\t"<<dist[i]<<="" p=""> } } int main() { int graph[vertex][vertex]={{0,5,3,0,0,0,0},{0,0,2,0,3,0,1},{0,0,0,7,7,0,0}, {2,0,0,0,0,6,0},{0,0,0,2,0,1,0},{0,0,0,0,0,0,0}, {0,0,0,0,1,0,0}}; dijkstra(graph,0); return 0; } Tegishli muammolar va algoritmlar. Dijkstra original algoritmining funktsiyalari turli modifikatsiyalar bilan kengaytirilishi mumkin. Masalan, ba'zida matematik jihatdan maqbul bo'lmagan echimlarni taqdim etish maqsadga muvofiqdir. Kamdan-kamroq optimal echimlar topilgan ro'yxatini olish uchun maqbul echim avval hisoblab chiqilgan. Optimal eritmada ko'rinadigan bitta qirrali grafadan chiqariladi va bu yangi grafikka optimal echim hisoblanadi. Dastlabki eritmaning har bir qirrasi o'z navbatida bekor qilinadi va yangi qisqa yo'l aniqlanadi. Keyinchalik, ikkilamchi eritmalar birinchi optimal eritmaning so'ng baholanadi va taqdim etiladi.Dijkstraning algoritmi, odatda, ulanish-davlat marshrutlash protokollari, OSPF va IS-IS eng keng tarqalgan bo'lib turadigan ish printsipi hisoblanadi.Dijkstra algoritmidan farqli o'laroq, Bellman-Ford algoritmi gorizontal manba vertolyotidan salbiy tsiklga ega$ $chap kismdagi uzgaruvchiga ta’minlaydi. B) Uzgaruvchilarga kiymat ta’minlaydi. C) Uzgaruvchilarning turini boshkasiga uzgartiradi. D) Ifoda qiymati qaysi turga mansubligini aniqlaydi. Deykstra algoritmi yordamida ikkita tepalik orasidagi eng qisqa masofani topish CD (CXDX, C2D2) nuqta sifatida tasvirlangan C5 \u003d D5 A5V5 teng darajada ... IKKI PARALLEL TEKISLIK ORASIDAGI MASOFANI ANIQLASH Umumiy holatdagi ikkita parallel tekislik orasidagi masofani aniqlash 01 | X uni proektorlarning holatiga aylangan bir xil ikkita samolyot orasidagi masofani aniqlash vazifasiga qisqartirish qulay. Bunday holda, tekisliklar orasidagi masofa to'g'ri chiziqlar orasidagi perpendikulyar, ... IKKITA KESIB O'TGAN TO'G'RI CHIZIQLAR ORASIDAGI MASOFANI ANIQLASH Agar siz ikkita kesish chizig'i orasidagi eng qisqa masofani aniqlashingiz kerak bo'lsa, proektsion tekisliklarning tizimlarini ikki marta o'zgartirishingiz kerak. Ushbu muammoni hal qilishda to'g'ri chiziq CD (CXDX, C2D2) nuqta sifatida tasvirlangan C5 \u003d D5 (rasm 198). Ushbu nuqtadan proektsiyagacha bo'lgan masofa A5V5 teng darajada ... IKKITA KESIB O'TGAN TO'G'RI CHIZIQLAR ORASIDAGI BURCHAK Bu ma'lumotlarga parallel ravishda ikkita kesishgan chiziq orasidagi burchak. Shunday qilib, bu vazifa oldingisiga o'xshashdir. Uni hal qilish uchun o'zboshimchalik bilan nuqta olish va u orqali berilgan kesishgan to'g'ri chiziqlarga parallel ravishda ikkita to'g'ri chiziq chizish kerak va proyeksiyalarning konvertatsiyasidan foydalanib kerakli burchakni aniqlang ... IKKALA PARALLEL TO'G'RI CHIZIQLAR ORASIDAGI MASOFANI ANIQLASH Muammo proektsion tekisliklarni ikki marta almashtirish bilan hal qilinadi. Oxirgi bosqichda proyeksiya tekisliklaridan biri kesishgan chiziqlardan biriga perpendikulyar bo'lishi kerak. Keyin ular orasidagi eng qisqa masofa perpendikulyar segmentning boshqa kesishish chizig'iga kattaligi bilan aniqlanadi ....$ $Dijkstra algoritmi - bu Gollandiyalik olim Edsger Deykstra tomonidan 1959 yilda ixtiro qilingan grafik asosidagi algoritm. Grafika tepalaridan birining qolgan qismiga qadar eng qisqa yo'llarni topadi. Algoritm ishlaydi faqat salbiy og'irlikdagi chekkalari bo'lmagan grafikalar uchun. 1-chi tepalikdan boshqalarga qadar eng qisqa masofani topish talab etilsin. Aylanalar tepaliklarni, chiziqlar ular orasidagi yo'llarni (grafik qirralarini) bildiradi. Tepaliklarning raqamlari doiralarda ko'rsatilgan, ularning "narxi" qirralarning yuqorisida - yo'lning uzunligi ko'rsatilgan. Har bir tepalik yonida qizil yorliq bor - bu tepalikka 1-tepalikdan eng qisqa yo'l uzunligi. Birinchi qadam ... Keling, misolimiz uchun Dijkstra algoritmining bir bosqichini ko'rib chiqaylik. 1 tepada minimal yorliq bor, uning qo'shnilari - 2, 3 va 6 tepaliklar. Birinchi navbatda birinchi vertikalning qo'shnisi vertex 2, chunki unga yo'l uzunligi minimaldir. Unga 1-vertikal orqali o'tadigan yo'l uzunligi 1-vertikal yorlig'i qiymati va 1-dan 2-gacha bo'lgan chekka uzunligi yig'indisiga teng, ya'ni 0 + 7 \u003d 7. 2-vertexning amaldagi yorlig'idan kam, abadiylik, shuning uchun 2- chi tepaliklarning yangi yorlig'i 7 ga teng. Biz xuddi shunday operatsiyani 1-chi vertikalning boshqa ikkita qo'shnisi - 3- chi va 6-chi bilan bajaramiz. 1 vertexning barcha qo'shnilari tekshiriladi. 1-cho'qqiga qadar bo'lgan minimal minimal masofa yakuniy hisoblanadi va qayta ko'rib chiqilmaydi (bu haqiqatan ham shunday ekanligini birinchi bo'lib E. Deykstra isbotlagan). Ushbu tepaga tashrif buyurganligini belgilash uchun uni grafikadan o'chirib tashlaymiz. Ikkinchi qadam ... Algoritm bosqichi takrorlanadi. Qayta ko'rilmagan tepaliklarning "eng yaqinini" yana toping. Bu vertikal 2, 7 bilan belgilangan. Biz yana tanlangan tepalik qo'shnilarining yorliqlarini kamaytirishga harakat qilamiz, ularga 2-tepalikdan o'tishga harakat qilamiz. 2 tepalikning qo'shnilari 1, 3 va 4 tepaliklaridir. 2 vertexning birinchi (tartibda) qo'shnisi - vertex 1. Ammo u allaqachon tashrif buyurgan, shuning uchun biz 1-vertex bilan hech narsa qilmaymiz. 2-vertexning keyingi qo'shnisi 3-vertexdir, chunki u tepaliklarning minimal yorlig'iga tashrif buyurilmagan deb belgilangan. Agar siz unga 2 orqali kirsangiz, unda bunday yo'lning uzunligi 17 ga teng bo'ladi (7 + 10 \u003d 17). Ammo uchinchi tepalikning amaldagi yorlig'i 9 ga teng, bu 17 dan kam, shuning uchun yorliq o'zgarmaydi.$ $2-vertexning yana bir qo'shnisi - 4-vertex. Agar siz unga 2-chi orqali borsangiz, u holda bunday yo'lning uzunligi 2-chi tepaga eng qisqa masofa va 2 va 4-tepalar orasidagi masofaning yig'indisiga teng bo'ladi, ya'ni , 22 (7 + 15 \u003d 22) ... 22 yildan beri<, устанавливаем метку вершины 4 равной 22. Barcha vertex 2-ning barcha qo'shnilari ko'rib chiqildi, masofani muzlatib qo'ying va tashrif buyurganingiz kabi belgilang. Uchinchi qadam ... Biz vertikal 3 ni tanlab algoritm qadamini takrorlaymiz. "Qayta ishlash" dan so'ng biz quyidagi natijalarga erishamiz: Keyingi qadamlar ... Qolgan tepaliklar uchun algoritm qadamini takrorlaymiz. Bu navbati bilan 6, 4 va 5 tepaliklar bo'ladi. Algoritm bajarilishini yakunlash ... Algoritm endi tepaliklarni qayta ishlash imkoni bo'lmaganda o'z ishini tugatadi. Ushbu misolda barcha tepaliklar chizib tashlangan, ammo har qanday misolda shunday bo'ladi deb ishonish xato - ba'zi cho'qqilar ularga etib borolmasa, ya'ni grafikani uzib qo'ygan bo'lsa, ularni kesib o'tmasdan qolishi mumkin. Algoritm natijasini oxirgi rasmda ko'rish mumkin: 1dan 2 gacha bo'lgan eng qisqa yo'l 7 ga, 3 ga 9 ga, 4 ga 20 ga, 5 ga 20 ga, 6 ga 11 ga teng. Algoritmni turli dasturlash tillarida amalga oshirish: C ++ #include "stdafx.h" #include std nom maydonidan foydalanish; const int V \ u003d 6; // Dijkstra algoritmi bekor Dijkstra (int GR [V] [V], int st) (int masofa [V], hisoblash, indeks, i, u, m \u003d st + 1; bool tashrif buyurdi [V]; uchun (i \ u003d 0; i <="min)" index="i;" u="index;" visited[u]="true;" gr[u][i]="" distance[u]!="INT_MAX" distance[u]+gr[u][i]<<" Стоимость ="" пути ="" из ="" начальной ="" вершины ="" до ="" остальных :\t\n";="" (distance[i]! ="INT_MAX)" cout<<m<<"="" style="box-sizing: inherit;">"<<i+1<<" =="" "<<distance[i]<<<m<<"="" style="box-sizing: inherit;"> "<<i+1<<" =="" "<<" маршрут ="" недоступен "<<<" Начальная ="" вершина ="" style="box- sizing: inherit;">\u003e "; cin \u003e\u003e start; Dijkstra (GR, start-1); tizim (" pauza \u003e\u003e bekor ");) PASKAL dastur DijkstraAlgoritm; crt dan foydalanadi; const V \u003d 6; inf \u003d 100000; vektor turi \u003d butun sonli massiv; var start: integer; const GR: butun sonli massiv \u003d ((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); (Dijkstra algoritmi) protsedurasi Dijkstra (GR: integer array; st: integer); var count, index, i, u, m, min: integer; masofa: vektor; tashrif buyurgan: mantiqiy qator; boshlang m: \u003d st; i: \u003d 1 dan V$ $gacha bo'lgan masofa boshlanadi [i]: \u003d inf; tashrif buyurilgan [i]: \u003d noto'g'ri; oxiri; masofa: \u003d 0; hisoblash uchun: \u003d 1 dan V-1 gacha min: \ u003d inf; uchun i: \u003d 1 dan V gacha, agar (tashrif buyurilmagan [i]) va (masofa [i])<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) va (masofa [u]<>inf) va (masofa [u] + GR <="" style="box-sizing: inherit;">inf then writeln (m, "\u003e", i, "\u003d", masofa [i]) else Writeln (m, "\u003e", i, "\u003d", "marshrut mavjud emas"); oxiri; (asosiy dastur bloki) boshlash clrscr; write ("Start vertex \u003e\u003e"); o'qish (boshlash); Dijkstra (GR, start); oxiri. JAVA import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution (private static int INF \u003d Integer.MAX_VALUE / 2; private int n; // digraph in the vertices of the number of private int m; // digray in the digraph in private ArrayList adj; // qo'shni ro'yxat xususiy ArrayList vazn; // ishlatiladigan maxsus boolean digrafidagi chekka og'irligi; // o'tgan va o'tmagan tepalar haqida ma'lumotni saqlash uchun massiv xususiy int dist; // boshlang'ich tepadan masofani saqlash uchun massiv // boshlang'ich tepadan eng qisqa yo'lni tiklash uchun zarur bo'lgan ajdodlar qatori private int pred; int start; // boshlang'ich tepalik, undan boshqalarga masofa xususiy BufferedReader cin; xususiy PrintWriter cout; xususiy StringTokenizer tokenizer; // Dijkstra algoritmini boshlang'ich tepadan xususiy void dejkstra (int s) dan boshlash tartibi (dist [s] \u003d 0; // boshlang'ich tepalikka eng qisqa masofa 0 uchun (int iter \u003d 0; iter)< n; ++iter) { int v = -1; int distV = INF; // выбираем вершину , кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } // рассматриваем все дуги , исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); // релаксация вершины if ( dist [ v ] + weightU < dist [ u ]) { dist [ u ] = dist [ v ] + weightU ; pred [ u ] = v ; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used [ v ] = true ; } } //процедура считывания входных данных с консоли private void readData () throws IOException { cin = new BufferedReader ( new InputStreamReader ( System . in )); cout = new PrintWriter ( System . out ); tokenizer = new StringTokenizer ( cin . readLine ()); n = Integer . parseInt ( tokenizer . nextToken ()); //считываем количество вершин графа m = Integer . parseInt ( tokenizer . nextToken ()); //считываем количество ребер графа start = Integer . parseInt ( tokenizer . nextToken ()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList [ n ]; for ( int i = 0; i < n ; ++ i ) { adj [ i ] = new ArrayList (); ) // qirralarning og ' irliklari saqlanadigan ro ' yxatning boshlanishi \ u 003 d yangi ArrayList [ n ]; uchun ( int i \ u 003 d 0; i < n ; + + i ) { weight [ i ] = new ArrayList (); ) // ( int i \ u 003 d 0; i uchun qirralarning ro ' yxati bilan belgilangan grafikani o ' qing < m ; ++ i ) { tokenizer = new$ $StringTokenizer ( cin . readLine ()); int u = Integer . parseInt ( tokenizer . nextToken ()); int v = Integer . parseInt ( tokenizer . nextToken ()); int w = Integer . parseInt ( tokenizer . nextToken ()); u --; v --; adj [ u ]. add ( v ); weight [ u ]. add ( w ); } used = new boolean [ n ]; Arrays . fill ( used , false ); pred = new int [ n ]; Arrays . fill ( pred , -1); dist = new int [ n ]; Arrays . fill ( dist , INF ); } //процедура восстановления кратчайшего пути по массиву предком void printWay ( int v ) { if ( v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } } Boshqa variant: Import java.io. *; import java.util. *; umumiy sinf Dijkstra (xususiy statik yakuniy Graph.Edge GRAPH \u003d (yangi Graph.Edge ("a", "b", 7), yangi Graph.Edge ("a", "c", 9)), yangi Graph.Edge ( "a", "f", 14), yangi Graph.Edge ("b", "c", 10), yangi Graph.Edge ("b", "d", 15), yangi Graph.Edge ("c" "," d ", 11), yangi Graph.Edge (" c "," f ", 2), yangi Graph.Edge (" d "," e ", 6), yangi Graph.Edge (" e ", "f", 9),); xususiy statik yakuniy String START \u003d "a"; xususiy statik yakuniy String END \u003d "e"; public static void main (String arggs) (Grafik g \ u003d yangi Grafika (GRAPH); g.dijkstra (START); g.printPath (END); //g.printAllPaths ();)) sinf Grafigi (shaxsiy yakuniy xarita grafik; // Edge to'plamidan qurilgan vertex moslamalariga vertex nomlarini xaritalash / ** Grafikning bir qirrasi (faqat Graf konstruktori foydalanadi) * / public static class Edge (public final String v1, v2; public final int dist; public Edge (String v1, String v2, int dist) (this.v1 \u003d v1; this.v2 \u003d v2; this.dist \u003d dist;)) / ** Grafikning bitta tepasi, qo'shni tepaliklarni xaritalash bilan to'ldirilgan * / jamoat statik klassi Vertex taqqoslashni amalga oshiradi (public final String name; public int dist \u003d Integer.MAX_VALUE; // MAX_VALUE cheksiz deb taxmin qilingan public Vertex previous \u003d null; public final Map qo'shnilar \u003d yangi HashMap<>(); public Vertex (string nomi) (this.name \u003d name;) private void printPath () (if (this \u003d\u003d this.previous) (System.out.printf ("% s", this.name);) else if ( this.previous \u003d\u003d null) (System.out.printf ("% s (unreaching)", this.name);) else (this.previous.printPath (); System.out.printf ("-\ u003e% s ( % d) ", this.name, this.dist);)) public int ComparTo (Vertex other) (return Integer.compare (dist, other.dist);)) / ** qirralarning to'plamidan grafik tuzadi * / umumiy grafik (qirralarning qirralari) (grafik \u003d yangi HashMap<>(qirralarning uzunligi); // (Edge e: qirralari) uchun barcha tepaliklarni topish uchun bitta o'tish (agar (! graph.containsKey (e.v1)) graph.put (e.v1, yangi Vertex (e.v1)); agar (! grafasi). containsKey (e.v2)) graph.put (e.v2, yangi vertex (e.v2));) // (Edge e: qirralari) uchun qo'shni tepaliklarni o'rnatish uchun yana bir$ $o'tish (graph.get (e.v1). qo'shnilar.put (graph.get (e.v2), e.dist); //graph.get(e.v2).neighbors.put(graph.get(e.v1), e.dist); // also buni yo'naltirilmagan grafik uchun bajaring)) / ** Belgilangan vertex * / public void dijkstra (String startName) (agar (! graph.containsKey (startName))) (System.err.printf ("Graph doesn" t start vertex o'z ichiga oladi \\ "% s \\" \\ n ", startName); return;) final vertex source \u003d graph.get (startName); NavigableSet q \u003d yangi TreeSet<>(); // (Vertex v: graph.values \u200b\ u200b()) (v.previous \u003d v \u003d\u003d manba? manba: null; v.dist \u003d v \ u003d\u003d manba? 0: Integer.MAX_VALUE; q. qo'shish (v);) dijkstra (q); ) / ** Ikkilik uyum yordamida dijkstra algoritmini amalga oshirish. * / Private void dijkstra (final NavigableSet q) (Vertex u, v; while (! q.isEmpty ()) (u \u003d q.pollFirst (); // eng qisqa masofaga ega bo'lgan vertex (birinchi takrorlash manbani qaytaradi), agar (u.dist \u003d\u003d Integer.MAX_VALUE)) break; // u (va boshqa har qanday tepaliklarni) e'tiborsiz qoldirishimiz mumkin, chunki ular ulanib bo'lmaydigan // har bir qo'shniga masofani ko'rib chiqing (Map.Entry a: u.neighbors.entrySet ()) (v \u003d a.getKey (); // bu iteratsiyadagi qo'shni final int alternateDist \u003d u.dist + a.getValue (); if (alternateDist< v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } } </i+1<<"></i+1<<"> C # shu jumladan # shu jumladan # shu jumladan // # BIG_EXAMPLE typedef struct node_t node_t, * heap_t ni belgilang; typedef struct edge_t edge_t; struct edge_t (node_t * nd; / * ushbu chekkaning maqsadi * / edge_t * birodar; / * yakka bog'langan ro'yxat uchun * / int len; / * chekka xarajatlar * /); struct node_t (edge_t * edge; / * qirralarning alohida bog'langan ro'yxati * / node_t * orqali; / * bu erda oldingi tugun eng qisqa yo'lda * / double dist; / * origining tugunidan masofa * / char nomi; / * the, er , name * / int heap_idx; / * masofani yangilash uchun uyum holatiga havola * /); / * --- qirralarni boshqarish --- * / #ifdef BIG_EXAMPLE # BLOCK_SIZE-ni aniqlang (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif edge_t * edge_root \u003d 0, * e_next \u003d 0; / * Xotirani boshqarish haqida o'ylamang, ular nuqta yonida. E_next \u003d malloc (sizeof (edge_t)) * / void add_edge (node_t * a, node_t * b, double d) (if (e_next \u003d\u003d edge_root) ) (edge_root \u003d malloc (sizeof (edge_t) * (BLOCK_SIZE + 1)); edge_root.sibling \u003d e_next; e_next \u003d edge_root + BLOCK_SIZE;) - e_next; e_next-\u003e nd \u003d b; e_next-\u003e len \u003d d; e_next -\u003e$ $aka-uka \u003d \u200b\u200ba-\u003e chekka; a-\u003e chekka \u003d e_next;) bo'sh bo'shliqlar () (uchun (; edge_root; edge_root \u003d e_next) (e_next \u003d edge_root.sibling; erkin (edge_root);)) / * --- ustuvor navbatdagi narsalar --- * / heap_t * heap; int heap_len; void set_dist (node_t * nd, node_t * via, double d) (int i, j; / * allaqachon yaxshi yo'lni bilar * / if (nd-\u003e via && d\u003e \u003d nd-\ u003e dist) return; / * mavjud uyum yozuvini toping yoki yangisini yarating * / nd-\u003e dist \u003d d; nd-\u003e orqali \u003d orqali; i \u003d nd-\u003e heap_idx; agar (! i) i \u003d ++ heap_len; / * upheap * / for (; i\u003e 1 && nd-\ u003e dist< heap->dist; i \u003d j) (heap [i] \u003d heap [j]) -\u003e heap_idx \ u003d i; heap [i] \u003d nd; nd-\u003e heap_idx \u003d i; ) node_t * pop_queue () (node_t * nd, * tmp; int i, j; agar (! heap_len) 0 qaytarsa; / * etakchi elementni olib tashlang, quyruq elementini o'sha joyga torting va pastga tushiring * / nd \u003d heap; tmp \u003d heap; for (i \u003d 1; i< heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist\u003e heap-\u003e dist) j ++; if (heap [j] -\ u003e dist\u003e \u003d tmp-\u003e dist) break; (heap [i] \u003d heap [j]) -\u003e heap_idx \u003d i; ) heap [i] \u003d tmp; tmp-\u003e heap_idx \u003d i; return nd; ) / * --- Dijkstra materiallari; erishib bo'lmaydigan tugunlar hech qachon qilmaydi ichiga navbat --- * / void calc_all (node_t * start) (node_t * lead; edge_t * e; set_dist (start, start, 0); while ((lead \u003d pop_queue ())) for (e \u003d lead-\ u003e edge; e; e \u003d e-\u003e aka-uka) set_dist (e-\u003e nd, qo'rg'oshin, qo'rg'oshin-\u003e dist + e-\u003e len);) bo'sh show_path (node_t * nd) (agar (nd-\ u003e orqali \u003d\u003d nd) printf ( "% s", nd-\u003e name); else if (! nd-\ u003e via) printf ("% s (unracaching)", nd-\u003e name); else (show_path (nd-\ u003e via); printf ("-) \u003e% s (% g) ", nd-\u003e name, nd-\u003e dist);)) int main (void) (#ifndef BIG_EXAMPLE int i; # define N_NODES (" f "-" a "+ 1) node_t * tugunlar \u003d calloc (sizeof (node_t), N_NODES); uchun (i \u003d 0; i< N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; } PHP$ $$ edge, "cost" \u003d\u003e $ edge); $ qo'shnilar [$ edge] \u003d array ("end" \u003d\u003e $ edge, "cost" \u003d\u003e $ edge); ) $ vertices \u003d array_unique ($ vertices); foreach ($ vertices $ vertex sifatida) ($ dist [$ vertex] \ u003d INF; $ oldingi [$ vertex] \u003d NULL;) $ dist [$ source] \u003d 0; $ Q \ u003d $ tepaliklar; while (count ($ Q)\u003e 0) (// TODO - Minimal $ min \u003d INF olishning tezroq usulini toping; foreach ($ Q $ $ vertex)) (if ($ dist [$ vertex])< $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n"; Xulosa Xulosa qilib aytganda Algoritm bilan ishlash barcha turdagi dasturlash tillarida ishlash uchun kerak buladi. Algoritmsiz biror bir dasturlash tilida dastur yaratib bulmaydi. Xar bir dasturning dastlab algoritmini yaratib olish zarur. Agar biz dasturimizning ketma-ketligini bilmasak , u dastur biz uylagandan kuproq xajmni egallashi mumkin ekan. Men C++ dasturlash tilida malumotlarni izlash , saralash, qayta ishlash kabi amallarni yuqorida kursatib utilganidagidek bir va ikki ulchovli massivlarda bajarilganini kurib bilim va kunikmalarga ega buldim. Men C++ dasturi strukturasi xaqida, belgilar bayoni, algoritm va dastur tushunchasi , malumotlarni kiritish va chiqarish operatorlari xamda dasturda ishlatiladigan toifalar, ifodalar va kunikmalarga ega buldim. Algoritmlash va dasturlash tillari buyicha yozilgan bir nechta kitoblar bilan tanishib chiqdim va ulardan uzimga kerakli malumotlarni oldim. Kurs ishimda Deyskra algoritmining ishlash prinsplarini ko’rib uning ishlashini dasturlarda amaliy ko’rib chiqdim.$ $13. Thorup, Mikkel (2000). "On RAM priority Queues". SIAM Journal on Computing. 30 (1): 86–109. doi : 10.1137/S0097539795288246 . 14. Thorup, Mikkel (1999). "Undirected single-source shortest paths with positive integer weights in linear time" . journal of the ACM. 46 (3): 362– 394. doi : 10.1145/316542.316548 . </c<<"\t\t"<<dist[i]<$

Mavzu: Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish. Reja: 1 . Kirish . 2. Asosiy qisim 1. Eng qisqa yo’llar masalalarining turlari. 2. Deykstra algoritmning so’zli tavsifi 3. Masalaning qo’yilishi. 4. Deysktra algoritmi. 3 . Xulosa. 4. Foydalanilgan adabiyotlar.

Kirish Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma- ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma-ketligi algoritm deb ataymiz. Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o‘rganadigan maxsus “Algoritmlar nazariyasi” bo‘limi xam mavjud. Algoritmlar nazariyasi – algoritmlarning umumiy xossalari , qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan shug'ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo‘llanilish sohasini aniqlash mumkin. Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu shahargacha sayohat qilishning eng qisqa yo'li nima? Bu yigirma daqiqada mo'ljallangan eng qisqa yo'l uchun algoritm. Bir kuni ertalab men yosh yigitlar bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe terastasiga o'tirdik va men buni qila olamanmi yoki yo'qmi deb o'ylagandim va keyinchalik eng qisqa yo'l uchun algoritmni yaratdim . Men aytganimdek, yigirma daqiqalik ixtiro bo'ldi. Darhaqiqat, u 59 yil ichida, uch yil o'tib nashr etildi. Bu kitob hali ham o'qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi bo'lgan sabablardan biri men uni qalam va qog'ozsiz tasvirladim. Keyinchalik bilib oldimki , qalam va qog'ozsiz loyihalashtirishning afzalliklaridan biri deyarli barcha oldini olish mumkin bo'lgan murakkabliklardan qochishingiz kerak. Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan. - Edzger Dijkstra, ACM bilan aloqa, Philip L. Frana, 2001. Dijkstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida eng qisqa yo'l muammosini o'ylab topdi.Uning maqsadi ham hisoblanmaydigan odamlar tushunishi mumkin bo'lgan muammoni va echimni (kompyuter tomonidan ishlab chiqariladigan) tanlash edi. U eng qisqa yo'l algoritmini ishlab chiqdi va undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan transport xaritasi uchun ARMAC uchun amalga oshirdi (64, ya'ni 6 bit shahar raqamini kodlash uchun etarli bo'ladi).Bir yil o'tgach, u institutning navbatdagi kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo'lgan simni kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi deb nomlanadigan algoritmni (avvalroq Jarnikka ma'lum va shuningdek, Primni qayta

kashf qilgan) kashf etdi. Dijkstra 1959 yilda, Primdan ikki yil keyin va Jarnikdan 29 yil o'tgach algoritmi nashr etdi. 1. Eng qisqa yo’llar masalalarining turlari. Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar. Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa irralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir. Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida , turdagi har bir uchlar juftliklari orasida va boshqalar. 2. Deykstra algoritmning so’zli tavsifi Eng qisqa masofani topish masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan. Algoritm quyidagi qa damlardan iborat: 1. Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi. 2. Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi). 3. Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi. 4. Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi. 5. BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi.

Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi. Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi. 3. Deyskra Algoritmi. Grafdagi eng qisqa marshrutlar uchun ko'plab qidiruv algoritmlari bo'yicha, Habreda faqatgina Floyd-Worschall algoritmining ta'rifi topildi. Ushbu algoritm grafikaning barcha vertikalari va ularning uzunligi o'rtasidagi eng qisqa yo'llarni topadi. Ushbu maqolada Dijkstra algoritmining ishlash printsipini tasvirlab beraman. Bu algoritm optimal yo'nalishlarni va ularning uzunligini ma'lum bir vertikal (manba) va grafikning boshqa vertikalari orasida topadi. Ushbu algoritmning nochorligi, agar grafika salbiy og'irliklarga ega bo'lsa, u noto'g'ri ishlaydi. Misol uchun, G quyidagi ko'rsatgichni bajaring: tasvirUshbu grafikani matritsa sifatida taqdim etamiz:tasvir Keling, vertex 1ni manba sifatida qabul qilaylik, shuning uchun vertex 1dan eng kichkina marshrutlarni 2, 3, 4 va 5-ustungacha topamiz.Ushbu algoritm grafaning barcha verticesida yineleyadi va manba verteksidan muayyan vertexga ma'lum minimal masofa bo'lgan belgilarga ularni belgilaydi. Masalan, ushbu algoritmni ko'rib chiqaylik.Keling, 1 tepalikka tegni 0 ga teng qilamiz, chunki bu vertex manba hisoblanadi. Qolgan tepaliklar abadiylikka teng teglar bilan belgilanadi. Keyinchalik, minimal yorlig'i (hozirda vertex 1) bo'lgan vertikal W ni tanlang va vertex W dan mediatorlar vertikalarini o'z ichiga olmaydi. W belgisining yig'indisiga teng bo'lgan belgini va hisobga olingan vertikalarning har biriga qarab, Vdan vertikaga yo'llarni belgilang, lekin natijada faqat oldingi qiymatdan kamroq bo'lsa. Agar bu miqdor kam bo'lmasa, oldingi belgini o'zgartirmang.Biz W dan to'g'ridan-to'g'ri yo'lni egallagan barcha vertikalarni ko'rib chiqdik, keyin V ga tashrif buyurib, tepaligini eng past qiymatga ega bo'lganlardan tanlaymiz va u keyingi V tepasida bo'ladi. Bu holda, bu birinchi 2 yoki 5. Agar bir xil teglar bilan bir necha vertikalar mavjud bo'lsa, ularning qaysi biri W ni tanlashimiz muhim emas. Biz vertex 2 ni tanlaymiz. Biroq, undan bitta chiqish yo'li yo'q, shuning uchun darhol ushbu vertexni tashrif buyurgan deb belgilab olamiz va keyingi vertikaga minimal belgisi bilan kiramiz. Bu safar faqat vertex 5da eng kam belgilar mavjud. 5-dan 5-gacha to'g'ridan-to'g'ri yo'llar mavjud bo'lgan barcha vertikalarni ko'rib

Ko'chirib oling, shunda to'liq holda ko'ra olasiz

O'xshashlar

TARMOQDA ENG QISQA MASOFANI TOPISH MASALASI (DYEKSTR ALGORITMI)

Graflarda eng qisqa masofani topish algoritmlari

Deykstra Algoritmi

GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR

Algoritmlarni loyihalash va tahlil qilish