Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.
![boshlanish nuqtasi bo'ladi va unga masofa (kesishma yorlig'i) nol bo'ladi. Keyingi
izlanishlar uchun (keyingi birinchi), joriy kesishish boshlang'ich nuqtaga eng yaqin
ko'rinmaydigan kesishish bo'ladi (bu oson topiladi).Joriy kesishuvdan to'g'ridan-
to'g'ri bog'langan har qanday ko'rinishdagi kesishma masofani yangilang. Buning
sababi, mavjud bo'lmagan kesishma va joriy kesishma qiymatlari o'rtasidagi
masofaning umumiy miqdorini belgilash va keyinchalik kiritilmagan kesishishning
ushbu qiymatga (summaga) kiritilmasligi, agar u kutilmagan kesishma oqimining
qiymatidan kamroq bo'lsa. Haqiqatdan ham, agar kesishma yo'li orqali unga yo'l
oldindan ma'lum bo'lgan yo'llardan qisqartirilsa, kesishma qayta belgilanadi. Eng
qisqa yo'lni identifikatsiyalashni engillashtirish uchun, qalamda yo'lni ko'rsatgich
bilan belgilab qo'ying va uni ko'rsatgan barcha belgilarni o'chirib tashlang. Har bir
qo'shni kesib o'tish joyiga masofani yangilaganingizdan so'ng, joriy kesishuvni
tashrif buyurilgan deb belgilang va eng kichik masofani (boshlang'ich nuqtadan)
yoki eng pastki belgini - mavjud kesishma sifatida tanlamang. Ko'rilgan deb
nomlangan uchastka boshlang'ich nuqtadan eng qisqa yo'l bilan etiketlanadi va
qayta ko'rib chiqilmaydi yoki qaytarilmaydi.
Qo'shni uchastkalarni eng qisqa masofalar bilan yangilab borish, mavjud
kesishishni tashrif buyurgan deb belgilash va maqsadni tashrif buyurgan deb
belgilaguningizcha eng yaqin ko'rinmaydigan kesma tomonga o'tish jarayonini
davom ettiring. Belgilangan joyni tashrif buyurganingiz kabi belgilab
qo'yganingizdan so'ng (siz tashrif buyurgan har qanday kesishmada bo'lgani kabi),
siz boshlash nuqtasidan eng qisqa yo'lni belgilab oldingiz va orqadagi o'qlar
orqasidan yo'lni orqaga qaytarasiz. Algoritmni amalga oshirishda, bu odatda tugma
tugunlaridan boshlang'ich tuguniga qadar tugunlarni ota-onalariga rioya qilish yo'li
bilan amalga oshiriladi (algoritm maqsadli tugunga yetgandan keyin); Shuning
uchun biz har bir tugunning ota-onasini kuzatib boramiz.Ushbu algoritm
kutilayotgan maqsadga yo'naltirilgan to'g'ridan-to'g'ri "qidiruv" harakatlariga yo'l
qo'ymaydi. Aksincha , kelgusi "joriy" kesishishni aniqlashda yagona e'tibor uning
boshlang'ich nuqtasigacha bo'lgan masofasidir. Shuning uchun ushbu algoritm
boshlang'ich nuqtadan tashqariga chiqadi, interaktiv ravishda maqsadga etgunga
qadar eng qisqa yo'l masofasi jihatidan yaqinroq bo'lgan har bir tugunni hisobga
oladi. Shu tarzda tushunilsa, algoritm qanday qilib eng qisqa yo'lni topish kerakligi
aniq. Shu bilan birga, u algoritmning zaif tomonlaridan birini ham ko'rsatishi
mumkin: ba'zi bir topologiyalardagi nisbiy sekinligi.
Dastur kodi
Quyidagi algoritmda kodi u ning vertex'si min dist [u] ga teng, u vertex
majmuasida eng kam dist [u] qiymati bo'lgan vertex u ni izlaydi. uzunligi (u, v)
ikki qo'shni n-tugunni u va v o'rtasidagi chegara uzunligini qaytaradi. 18-satrda
o'zgaruvchining pastki qismi - ildiz tugunidan qo'shni tugunga yo'lning uzunligi v
U orqali o'tish kerak edi. Ushbu yo'l v uchun saqlangan joriy qisqa yo'ldan
qisqartirsa, u joriy yo'l bu pastki yo'l bilan o'zgartiriladi. Avvalgi qator manbaga](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_7.png)
![#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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_10.png)
![// 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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_11.png)
![// 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}](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_12.png)
![};
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;
}](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_13.png)
![}
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])<>](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_14.png)
![}
}
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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_15.png)
![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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_19.png)
![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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_20.png)
![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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_21.png)
![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](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_23.png)
![$ 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.](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_24.png)
![3. Тыугу Х. Концептуальное программирование. М: Наука, 1984.
4. Н. Вирт. Алгоритмы и структуры данных. – Досса, Хамарайан, 1997.
5. Cormen , Thomas H . ; Leiserson , Charles E . ; Rivest , Ronald L . ; Stein ,
Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to
Algorithms (Second ed.). MIT Press and McGraw–Hill . pp. 595–601. ISBN 0-262-
03293-7 .
6. Dial, Robert B. (1969). "Algorithm 360: Shortest-path forest with topological
ordering [H]". Communications of the ACM . 12 (11): 632–
633. doi : 10.1145/363269.363610 .
Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Fibonacci heaps and their
uses in improved network optimization algorithms. 25th Annual Symposium on
Foundations of Computer Science. IEEE . pp. 338–
346. doi : 10.1109/SFCS.1984.715934 .
7. Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Fibonacci heaps and
their uses in improved network optimization algorithms" . Journal of the
Association for Computing Machinery. 34 (3): 596–
615. doi : 10.1145/28869.28874 .
8. Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path
Algorithms: An Evaluation Using Real Road Networks". Transportation
Science . 32 (1): 65–73. doi : 10.1287/trsc.32.1.65 .
9. Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.;
Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First
Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques
for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
10. Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information
Processing Letters . 6 (1): 1–5. doi : 10.1016/0020-0190(77)90002-3 .
11. Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (April
1990). "Faster Algorithms for the Shortest Path Problem". Journal of the
ACM. 37 (2): 213–223. doi : 10.1145/77600.77615 .
12. Raman, Rajeev (1997). "Recent results on the single-source shortest paths
problem". SIGACT News. 28 (2): 81–87. doi : 10.1145/261342.261352 .](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_26.png)
![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]<](/data/documents/aaa6abd0-e92c-4183-a3a9-9243102c4ff2/page_27.png)
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
chiqing, ammo hozircha ular tashrif buyurilgan deb bo'lmaydi. Shunga qaramay , vertex W yorlig'ining yig'indisi va W dan joriy vertexning chekkasini topamiz va agar bu summa oldingi yorliqdan kamroq bo'lsa, biz natijada olingan qiymat bilan etiketaning qiymatini o'zgartiramiz. Rasmga asoslanib, biz uchinchi va to'rtinchi zirvalarning yorliqlari kichikroq ekanligini, ya'ni manba tepasidagi bu tepaliklarga nisbatan qisqaroq yo'lni topdik. Keyinchalik, 5 vertexni tashrif buyurgan deb belgilang va eng past belgisi bo'lgan keyingi vertikani tanlang. Yuqorida keltirilgan barcha harakatlar takrorlanmagan vertikalar mavjud ekan, takrorlang. Barcha amallarni bajarib bo'lgach, biz quyidagi natijani qo'lga kiritamiz: Dijkstra algoritmi Grafikdagi ma'lum bir manba tuguniga ega bo'lgan algoritm bu tugun bilan har bir boshqa o'rtasidagi eng qisqa yo'lni topadi. Bundan tashqari, bitta tugunning eng qisqa yo'llarini to'xtatish yo'li bilan bitta maqsadli tugunga maqsad tuguniga eng qisqa yo'l aniqlanganidan keyin algoritm aniqlandi. Masalan, agar grafika tugunlari shaharlarni ifodalasa va chekka xarajatlari to'g'ridan-to'g'ri yo'l bilan bog'langan shaharlarning juftliklari o'rtasidagi masofani ifodalaydi (oddiylik uchun, qizil chiroqlar, ishlamaydigan belgilar, pullik yo'llar va boshqa to'siqlarni e'tiborsiz qoldirish uchun), Dijkstra algoritmi ishlatilishi mumkin Bir shahar va boshqa shaharlarning eng qisqa yo'lini topish. Qisqa yo'l algoritmining keng tarqalgan qo'llanilishi tarmoqni boshqarish protokollaridir , Shuningdek, Jonson kabi boshqa algoritmlarda ham subroutin sifatida qo'llaniladi. Dijkstra algoritmida musbat tamsayı yoki haqiqiy sonlar bo'lgan etiketlar ishlatiladi, bu aniq zaif tartibga solingan. Qiziqarli tomoni shundaki, Dijkstra aniq belgilangan qisman tartibga ega bo'lgan va keyingi teglar (bir chekkadan o'tib ketganda keyingi yorliq) monotonik ravishda kamaymaslik sharti bilan aniqlangan teglardan foydalanish uchun umumlashtirilishi mumkin. Ushbu umumlashma umumiy Dijkstra qisqa yo'l algoritmi deb ataladi. Bu asimptotik jihatdan cheklanmagan bo'lmagan grafikalar uchun eng tez-tez ma'lum bo'lgan yagona manbali eng qisqa yo'l algoritmidir. salbiy og'irliklar. Shu bilan birga, ixtisoslashgan variantlar (masalan, cheklangan / to'liq sonlar, yo'naltirilgan asiklik grafikalar va h.k.) ixtisoslashgan variantlarda batafsil ravishda takomillashtirilishi mumkin.Ba'zi sohalarda, xususan sun'iy aql, Dijkstra algoritmi yoki uning bir nusxasi bir xil xarajat qidiruvi deb nomlanadi va eng yaxshi qidiruvga oid umumiy g'oyaning misoli sifatida shakllanadi.Algoritm Dijkstra algoritmining robot harakati rejalashtirishda boshlang'ich tugunidan (pastki chap, qizil) maqsad tuguniga (yuqori o'ng, yashil) yo'l topish. Ochiq tugunlar "noaniq" to'plamni aks ettiradi ("novisited" tugunlar to'plami). To'ldirilgan tugunlar tashrif