Toshpulatov Jasurbekning "Algoritmlarni loyihalash"

M ta uch va N ta qirralardan iborat uzluksiz grafda V₀ uchidan W uchigacha Dist(W) masofani topish kerak. Qirralar uzunliklari A matrisa bilan berilgan deb hisoblaymiz. Qadam 0. [uchlarni belgilash] – bu yerda V₀ uchini “aniqlangan” deb belgilaymiz, qolgan barcha uchlarini “aniqlanmagan” deb hisoblaymiz.
Qadam 1. [o’zgaruvchilarni inetsiallashtirish] – bu yerda Dist(U):=A(V_{0 ,}U) - barcha G ga tegishli U uchlari uchun;
Dist(V_{0 0}):=0; Next:=V₀;
_{Qadam 2. [sikl]. While NEXT<>W do
Begin
Qadam 3 [}“aniqlanmagan” uchgacha eng qisqa yo’lni yangilash]. Har bir “aniqlanmagan” U uchi uchun Dist(U):=min(Dist(U):Dist(Next)+A(Next, U)). Qadam 4. [“aniqlanmagan” uchgacha eng qisqa yo’lni tanlash]. Agar U barcha “aniqlanmagan” uchlari orasida Dist(U) masofasi eng kichik bo’lsa, uni “aniqlangan” deb belgilaymiz va NEXT:=U.
end.
_{Bu algoritmning va dasturning murakkabligini} O(M²) ekanligini ko’rsatish mumkin.

Masalaning qo’yilishi: berilgan n = 4, e = 6 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3 grafning 2 uchidan boshlab chuqurligini aniqlash;

• 
  Masalaning quyilishi: berilgan n = 4, e = 6 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3 grafning 2 uchidan boshlab chuqurligini aniqlash;
  
• 
  Dastur kodi:#include
  
• 
  using namespace std;
  
• 
  class Graph
  
• 
  {
  
• 
  int V; list *adj;
  
• 
  void DFSUtil(int v, bool visited[]);
  
• 
  public:
  
• 
  Graph(int V); // Constructor
  
• 
  // function to add an edge to graph
  
• 
  void addEdge(int v, int w);
  
• 
  void DFS(int v);
  
• 
  };
  
• 
  Graph::Graph(int V){ this->V = V;
  
• 
  adj = new list[V];
  
• 
  } void Graph::addEdge(int v, int w){ adj[v].push_back(w);} void Graph::DFSUtil(int v, bool visited[]){ visited[v] = true;cout << v << " ";
  
• 
  list::iterator i;
  
• 
  for (i = adj[v].begin(); i != adj[v].end(); ++i)
  
• 
  if (!visited[*i])
  
• 
  DFSUtil(*i, visited);
  
• 
  }