Алгоритм Дейкстры: кратчайшие пути со взвешенными рёбрами

      1
      class MinHeap {
    

      2
      constructor() { this.items = []; }
    

      3
      size() { return this.items.length; }
    

      4
       
    

      5
      push(item) {              // item = [distance, vertex]
    

      6
        const a = this.items;
    

      7
        a.push(item);
    

      8
        let i = a.length - 1;
    

      9
        while (i > 0) {          // sift up to keep min at the root
    

      10
          const parent = (i - 1) >> 1;
    

      11
          if (a[parent][0] <= a[i][0]) break;
    

      12
          [a[parent], a[i]] = [a[i], a[parent]];
    

      13
          i = parent;
    

      14
        }
    

      15
      }
    

      16
       
    

      17
      pop() {                   // remove and return the smallest
    

      18
        const a = this.items;
    

      19
        const top = a[0];
    

      20
        const last = a.pop();
    

      21
        if (a.length > 0) {
    

      22
          a[0] = last;
    

      23
          let i = 0; const n = a.length;
    

      24
          while (true) {         // sift down to restore heap order
    

      25
            let smallest = i;
    

      26
            const l = 2 * i + 1, r = 2 * i + 2;
    

      27
            if (l < n && a[l][0] < a[smallest][0]) smallest = l;
    

      28
            if (r < n && a[r][0] < a[smallest][0]) smallest = r;
    

      29
            if (smallest === i) break;
    

      30
            [a[smallest], a[i]] = [a[i], a[smallest]];
    

      31
            i = smallest;
    

      32
          }
    

      33
        }
    

      34
        return top;
    

      35
      }
    

      36
      }
    

• L5 Каждый элемент это [distance, vertex]; мы упорядочиваем по item[0], расстоянию.
• L9 Просеивание вверх: всплывай новый элемент к корню пока его родитель не станет меньше.
• L18 pop() всегда возвращает пару с наименьшим расстоянием: ближайшую вершину фронта.
• L24 Просеивание вниз: спускай перемещённый последний элемент назад на его правильный уровень.
• L27 Сравни обоих детей и поменяй с меньшим, повторяя пока не установится.

      1
      function dijkstra(source, adj) {
    

      2
      const dist = {};
    

      3
      const parent = {};
    

      4
      for (const v in adj) dist[v] = Infinity; // unknown = infinity
    

      5
      dist[source] = 0;                        // source is 0 from itself
    

      6
      parent[source] = null;
    

      7
       
    

      8
      const settled = new Set();
    

      9
      const heap = new MinHeap();
    

      10
      heap.push([0, source]);
    

      11
       
    

      12
      while (heap.size() > 0) {
    

      13
        const [d, u] = heap.pop();        // closest unsettled vertex
    

      14
        if (settled.has(u)) continue;     // stale entry: skip (lazy deletion)
    

      15
        settled.add(u);                   // u's distance is now FINAL
    

      16
       
    

      17
        for (const [v, w] of adj[u]) {    // relax each outgoing edge
    

      18
          if (dist[u] + w < dist[v]) {
    

      19
            dist[v] = dist[u] + w;        // cheaper route to v found
    

      20
            parent[v] = u;                // remember the breadcrumb
    

      21
            heap.push([dist[v], v]);      // push, do NOT decrease-key
    

      22
          }
    

      23
        }
    

      24
      }
    

      25
      return { dist, parent };
    

      26
      }
    

• L4 Каждая вершина начинается с бесконечности: маршрут пока неизвестен.
• L5 Источник стоит 0 чтобы достичь его от самого себя.
• L8 settled = вершины, чьё итоговое расстояние зафиксировано. Управляет пропуском ниже.
• L13 Если u уже установлена, это устаревший дубликат; игнорируй его.
• L14 Установка u фиксирует dist[u] как итоговое: инвариант установки.
• L17 Тест релаксации: обыгрывает ли маршрут через u лучший известный к v?
• L18 Понижай dist[v] только когда строго дешевле, так мы никогда не раздуваем расстояние.
• L20 Нет decrease-key: добавь свежую (меньшую) запись; старая становится устаревшей.

      1
      function reconstructPath(target, parent) {
    

      2
      const path = [];
    

      3
      let cur = target;
    

      4
      while (cur !== null && cur !== undefined) {
    

      5
        path.push(cur);        // collect target back to source
    

      6
        cur = parent[cur];     // step to the predecessor
    

      7
      }
    

      8
      path.reverse();          // flip to read source -> target
    

      9
      return path;
    

      10
      }
    

• L4 null помечает источник; undefined означает что цель не была достигнута.
• L5 Мы собираем вершины в обратном порядке: цель сначала, источник последним.
• L8 Переверни чтобы получить естественное направление источник-к-цели.