Dijkstra's Algorithm

Rasmda berilgan graph Vaznli graph (weighted graph) deyiladi. Bunday graphlarning bir nuqtasidan boshqa nustasigacha bo'lgan vazni bo'ladi (rasmda bir nuqtalar orasidagi masofa keltirilgan). Bunday graphlarda ikki nuqta orasidagi eng kichik masofani topishlik uchun "Dijkstra algoritmi" ishlatiladi. BFS (breadth first search) algoritmi bilan bir nuqtadan ikkinchi nuqtaga olib boruvchi eng kichik yo'lni topgan bo'lsak (unda masofalar yo'q edi, segmentlar bor edi), Dijkstra algoritmi bilan eng kichik masofani topib olamiz.

Quyida weigthed graph va Dijkstra algoritmining codedagi implementatsiyasini ko'rob chiqamiz:

type WeightedGraphType = Record<string, Record<string, number>>

class WeightedGraph {

  private graph: WeightedGraphType
  constructor () {    
    this.graph = {}  
  }

  print () {    
    return this.graph  
  }
  // graphga uzel (edge) lar qo'shish uchun
  addEdge (key: string, value: Record<string, number>) {    
     this.graph[key] = value  
  }
  // start nuqtadan qolgan barcha nuqtalargacha bo'lgan
  // masofani qaytaradi
  dijkstra(start: string): Record<string, number> {
     // start nuqtadan qolgan barcha nuqtalargacha bo'lgan eng    
     // kichik masofani saqlash uchun     
     const distances: Record<string, number> = {};
     
     // tashrif buyurilgan nuqtalarni saqlash uchun    
     const visited = new Set<string>();

     // graph keylarini massivga olamiz // ['a', 'b' ..., 'g']    
     let nodes = Object.keys(this.graph);

     // har bir nuqta uchun boshlang'ich masofani Inifinity     
     // qilib belgilab olamiz
     for (let node of nodes) {        
         distances[node] = Infinity;    
     }

     // boshlang'ich nuqtadan o'zigacha bo'lgan masofa    
     // 0 bo'lgani uchun uni 0 ga tenglaymiz
     distances[start] = 0;

     // barcha nodelar bo'ylab siklda aylanib chiqamiz    
     while (nodes.length) {
       // nodelarni kamayish tartibida tartiblab olamiz va        
       // undan eng yaqin bo'lgan nodeni olamiz
       nodes.sort((a, b) => distances[b] - distances[a]);        
       let closestNode = nodes.pop()!;
       
       // agar eng yaqin nodegacha bo'lgan masoda hali ham Infinity bo'lsa,        
       // u holda u siklni to'xtatamiz
       if (distances[closestNode] === Infinity) {          
           break        
       }
       
       // eng yaqin node'ni tashrif buyurilganlarga qo'shamiz        
       visited.add(closestNode);
       
       // node'ning har bir qo'shnilari bo'ylab yurib chiqamiz        
       for (let neighbor in this.graph[closestNode]) {
          // agar qo'shni node'ga hali tashrif buyurilmagan bo'lsa            
          if (!visited.has(neighbor)) {                
            // node'dan uning qo'shinisigacha bo'lgan masofani hisoblaymiz                
            let newDistance = distances[closestNode] + this.graph[closestNode][neighbor];                                
            // agar hisoblangan masofa ayni paytdagi masofadan kichik bo'lsa                
            // u holda ayni masofani o'zgartiramiz (eng kichik masofa)                
            if (newDistance < distances[neighbor]) {                    
               // eng kichik masofani update qilamiz                    
               distances[neighbor] = newDistance;                
            }            
          }        
       }
     }
    // start nuqtadan qolgan nuqtalargacha (nodelar) bo'lgan eng     
    // kichik masofalarni qaytaramiz    
    return distances;
  } 

  // bir nuqtadan ikkinchi nuqtagacha bo'lgan eng kichik masofa
  shortDistance (start: string, end: string): number | undefined {
     return this.dijkstra(start)[end]
  }   
}

// Weighted graph instance
const weightedGraph = new WeightedGraph()

// uzel (edge) larni qo'shib chiqamiz
weightedGraph.addEdge('a', {b: 2, c: 1})
weightedGraph.addEdge('b', {f: 7})
weightedGraph.addEdge('c', {d: 5, e: 2})
weightedGraph.addEdge('d', {f: 2})
weightedGraph.addEdge('e', {f: 1})
weightedGraph.addEdge('f', {g: 1})
weightedGraph.addEdge('g', {})

console.log(weightedGraph.print())
// {
//   a: { b: 2, c: 1 },
//   b: { f: 7 },
//   c: { d: 5, e: 2 },
//   d: { f: 2 },
//   e: { f: 1 },
//   f: { g: 1 },
//   g: {}
// }

console.log(weightedGraph.dijkstra('a')) // { a: 0, b: 2, c: 1, d: 6, e: 3, f: 4, g: 5 }
// a nuqtadan g nuqtagacha bo'lgan masofani topish
console.log(weightedGraph.shortDistance('a', 'g')) // 5

Telegram kanalim: https://t.me/elyor_dev