Oliy va o`rta maxsus ta`lim vazirligi Samarqand Davlat Universiteti

5.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 eng qisqa yo'lni olish uchun manba grafasida "keyingi-hop" tuguniga ko'rsatgich bilan to'ldiriladi.




Agar vertices manbai va maqsad o'rtasida eng qisqa yo'l bilan qiziqsak, agar u = maqsad bo'lsa, 15-sathdan keyin qidiruvni tugatishimiz mumkin. Keling, biz qaytadan ierarxiya orqali manbaga eng qisqa yo'lni o'qiy olishimiz mumkin:

3.//Faqat vertexga o'tish mumkin bo'lsa, biror narsani bajaring.

4.//S-to'plam bilan eng qisqa yo'lni tanlang.

5.//Tepalikka suyakka suring.

6.// maqsaddan manbaga aylantirish.

2//boshlash.

8//V manbadan tortib v. Ga noma'lum masofa.

9//Predessori v.

14//Asosiy ko'chadan.

15//Eng yaxshi vertexni olib tashlang.

16//faqat v ning hali ham Q.

Boshlash davridagi barcha tugunlar bilan ustuvor navbatni to'ldirishning o'rniga, uni faqat manbai bo'lishi uchun ishga tushirish mumkin; unda, agar pastki

С++ dasturlash tilida quyidagicha bo’ladi:

1-ko’rinish

// A C++ program for Dijkstra's single source shortest path algorithm.

// The program is for adjacency matrix representation of the graph

#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

{

if(Dset[v]==false && dist[v]<=min)

{

min=dist[v];

index=v;

}

}

return index;

}

void dijkstra(int graph[vertex][vertex],int src) /*Method to implement shortest path algorithm*/

{

int dist[vertex];

bool Dset[vertex];

for(int i=0;i

{

dist[i]=INT_MAX;

Dset[i]=false;

}

dist[src]=0; /*Initialize the distance of the source vertec to zero*/

for(int c=0;c

{

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

/*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]=dist[u]+graph[u][v];

}

}

cout<<"Vertex\t\tDistance from source"<

for(int i=0;i

{

char c=65+i;

cout<

}

}

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;

}

6.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 bo'lmasa, salbiy qirrali grafika bilan ishlatilishi mumkin. Bunday aylanishlarning mavjudligi eng kichik yo'l yo'qligini anglatadi, chunki har bir tsiklda aylanish jarayonida umumiy og'irlik pastga aylanadi. Dijkstra algoritmini salbiy og'irlik chekkalarini Bellman-Ford algoritmiga (salbiy qirralarni olib tashlash va salbiy davrlarni aniqlash) birlashtirish yo'li bilan moslashtirish mumkin, bunday algoritm Jonsonning algoritmi deb ataladi.

A * algoritmi Dijkstra ning algoritmini umumlashtirish, agar maqsadga "masofadan" pastroq bo'lgan cheklovni ta'minlaydigan qo'shimcha ma'lumot mavjud bo'lsa, o'rganilishi kerak bo'lgan subgraf o'lchamini qisqartiradi. Ushbu yondashuv chiziqli dasturlash nuqtai nazaridan qaralishi mumkin: eng qisqa yo'llarni hisoblash uchun tabiiy chiziqli dastur mavjud va uning ikkilamchi chiziqli dasturiga echimlarni kiritish mumkin va ular faqat izchil sezgirlikni shakllantirsa (taxminan, so'zma-so'z konventsiyalari farqlanadi) adabiyotda joydan joygacha). Ushbu mumkin bo'lgan ikkilangan / izchil topilmalar salbiy bo'lmagan past narxni belgilaydi va A * bu Dijkstra algoritmini ushbu kam xarajatlar bilan boshqaradi. Agar ikkilamchi qabul qilishning zaif holatini qondirsa, A * o'rniga Bellman-Ford algoritmiga ko'proq mos keladi.

Dijkstraning algoritmining asoslanishi jarayon Primet algoritmida ishlatiladigan ochko'z jarayonga o'xshaydi. Primning maqsadi grafadagi barcha tugunlarni bir-biriga bog'lovchi minimal spanning daraxtni topishdir; Dijkstra faqat ikkita tugun bilan bog'liq. Primer, yo'lning umumiy og'irligini boshlang'ich tugunidan, faqatgina individual qirralarni baholaydi.Kichkina birinchi qidiruvni Dijkstra algoritmini taqqoslanmagan graflarda ko'rib chiqish mumkin, bu erda navbatdagi navbat FIFO navbatiga ziyon beradi.Tez marshing usuli Dijkstra algoritmining uchburchak meshidagi geodezial masofani hisoblaydigan uzluksiz versiyasidir.

7.Eng qisqa masofani toppishga doir testlar

ifoda kiymatini xisoblash uchun keltirilgan shartli operatorlardan kaysi biri tugri? 
 A) Keltirilgan operatorlardan xech biri berilgan ifodani tugri xisoblamaydi.   
B) If y<0 then Begin x<0 then N:=3 else N:=4End   
    else If x<0 then N:=2 else N:=1;  
C) If (y>=0) and (x>=0) then N:=1 else N:=2;   
    If (y<0) and (x<0) then N:=3 else N:=4;  
D) If x<0 then Begin y<0 then N:=1 else N:=2 End   
    else Begin If y>=0 then N:=3 else N:=4 End ;  
5.  Ta’minlash operatori kanday ishni bajarish uchun muljallangan? Eng umumiy javobni toping. 
A)  Operatorning  ung  kismida  turgan    ifodani  xisoblaydi  va  uning  kiymatini  chap  
kismdagi uzgaruvchiga ta’minlaydi.   
B) Uzgaruvchilarga kiymat ta’minlaydi.  
C) Uzgaruvchilarning turini boshkasiga uzgartiradi.  

D) Ifoda qiymati qaysi turga mansubligini aniqlaydi.   

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.

  

Foydalangan adabiyotlar:

• 
  Adabiyotlar 
   В.А.Успенский,  А.Л.Семенов.  Теория  алгоритмов:  основные  открытия  и  
  приложения. – М: Наука, 1987, 287 с.  
  2.  Т..Кормен,  Ч.Лейзерсон,  Р.Ривест.  Алгоритмы:  построение  и  анализ Сер:Классические учебники. М.: МЦНМО, 2001.- 960 с.  
  3.  Тыугу Х. Концептуальное программирование. М: Наука, 1984.  
  4.   Н. Вирт. Алгоритмы и структуры данных. – Досса, Хамарайан, 1997.  
  

• 
  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.
  
• 
  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.
  
• 
  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.
  
• 
  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.
  
• 
  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.
  
• 
  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.
  
• 
  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.
  
• 
  Raman, Rajeev (1997). "Recent results on the single-source shortest paths problem". SIGACT News. 28 (2): 81–87. doi:10.1145/261342.261352.
  
• 
  Thorup, Mikkel (2000). "On RAM priority Queues". SIAM Journal on Computing. 30 (1): 86–109. doi:10.1137/S0097539795288246.
  
• 
  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.