Algoritmdan nazorat savollariga javoblar Algoritm nima

43..#### Deykstra algoritmi

Bir uchdan boshqa uchlarga boradigan eng qisqa yo’llar(Deykstra algoritmi)

Masala qoyilishi

• 
  n ta uchli va m ta qirraga ega bo’lgan orietrlangan yoki orintrlanmagan graf berilgan. Qandaydir boshlang’ich uch ko’rsatilgan. uchdan boshqalarigacha bo’lgan eng qisqa masofalarni toppish kerak va yo’lning o’zinin ham chiqarish talab etiladi.
  
• 
  Bu masala “yagona manbaali eng qisqa yo’llarni izlash masalasi” (single-source shortest paths problem) deyiladi.
  
• 
  Algoritm Daniyalik tadqiqodchi Edsger Deykstra (Dijkstra) tamonidan 1959 yilda ishlab chiqilgan
  

Malumotlar kiritsh

• 
  cin >> n >> m;
  
• 
  for (int i = 1; i <= m; i++) {
  
• 
  int v1, v2, c;
  
• 
  cin >> v1 >> v2 >> c;
  
• 
  a[v1][v2] = a[v2][v1] = c;
  
• 
  }
  

• 
  int dijkstra(int start, int finish) {
  
• 
  for (int i = 1; i <= n; i++) {
  
• 
  d[i] = INF;
  
• 
  used[i] = 0;
  
• 
  }
  
• 
  d[start] = 0;
  
• 
  for (int it = 1; it <= n; it++) {
  
• 
  int v = 0;
  
• 
  for (int i = 1; i <= n; i++) {
  
• 
  if (!used[i] && (v==0 || d[i] < d[v]))
  
• 
  v = i;
  
• 
  }
  
• 
  }
  
• 
  used[v] = 1;
  
• 
  for (int i = 1; i <= n; i++) {
  
• 
  if (a[v][i] > 0)
  
• 
  d[i] = min(d[i], d[v] + a[v][i]);
  
• 
  }
  
• 
  }