Dijkstra's Algorithm

2024-01-06T12:48:42.886Z

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

#dijkstras_algorithm

#algorithm

#elyor_dev

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

Linked List (bog'langan ro'yxat)

2023-12-25T16:51:20.428Z

Linked List - bu data strukturalardan biri bo'lib undagi bir element o'zidan keyingi elementga linkni saqlaydi. Misol uchun:

const list = {
   value: 1,
   next: {
     value: 0,
     next: {
       value: 3,
       next: {
          .......
       }
     }
   }
}

Yuqoridagi rasmda massiv va linked list ustida amallarning (o'qish, element qo'shish, o'chirish) bo'yicha tezligi keltirilgan.

Quyida linked listning bir elementini generatsiya qilib beradigan class keltirilgan:

 class ListNode {    
    val: number    
    next: ListNode | null // keyingi element   
     
    constructor(val?: number, next?: ListNode | null) {        
        this.val = (val === undefined ? 0 : val)        
        this.next = (next === undefined ? null : next)    
    }
 }

Massivdagi sonlardan Linked List yasab chiqamiz:

const temp = [0, 1, 2, 3, 4, 5]

function generateLinkedList(arr: number[]): ListNode | null {
  if (arr.length === 0) {    
    return null  
  }

  const head = new ListNode(arr[0])  
  let current = head

  for (let i = 1; i < arr.length; i++) {    
    const newNode = new ListNode(arr[i])    
    current.next = newNode    
    current = newNode  
  }

  return head
  
}

const list = generateLinkedList(temp) //{val: 0, next: {val: 1, next: ...}}

LinkedList classini yozamiz:

class LinkedList {    
  head: ListNode | null    
  private _size: number // Linked Listning o'lchamini saqlaymiz.

    constructor() {        
      this.head = new ListNode()        
      this._size = 0    
    }

    // listni uzunligini qaytaradi    
    get size () {        
      return this._size    
    }

    // kerakli indexga element qo'shish
    insertAt(element: number, index: number) {
      if (index < 0 || index > this.size) {
        return console.log("Mavjud bo'lmagan index");
      }

      // Yangi node yaratib olamiz
      let node = new ListNode(element)            
      let curr = this.head          
      let prev: ListNode | null = null

      // Agar birinchi element bo'lsa            
      // ortiqcha sikl kerak emas
      if (index == 0) {                
          node.next = this.head;                
          this.head = node;            
      } else {                
         curr = this.head;                
         let it = 0;

         while (it < index) {
           it++;                    
           prev = curr;                    
           curr = curr?.next || null;
         }

         // element qo'shish                
         node.next = curr;                
         prev!.next = node;
       }

       this._size++
    }
}

To'liqroq ma'lumot olish uchun: https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/

#linked_list #data_structure #algorithms

@elyor_dev