Що таке зважений граф?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Зважений граф - це граф, у якому кожному ребру (іноді вершині) відповідає числове значення - вага. Вага зазвичай означає вартість, відстань, час, пропускну здатність або ймовірність і використовується під час обчислення шляхів, остовів та інших характеристик графа.

Розгорнута відповідь

Формальне визначення

Зважений граф - це трійка G = (V, E, w), де V - множина вершин, E - множина ребер (впорядкованих для орієнтованого графа і невпорядкованих для неорієнтованого), а w - функція ваг. Найчастіше w задає ваги на ребрах: w: E → R (дійсні числа). Іноді використовують ваги на вершинах: w: V → R, або одночасно на вершинах і на ребрах.

Орієнтований і неорієнтований: зважування застосовне в обох випадках.
Діапазон ваг: ваги можуть бути додатними, нульовими або від'ємними (залежно від задачі й алгоритму).
Невзважений граф - окремий випадок, де всі ваги дорівнюють 1 (або іншій однаковій константі).

Навіщо потрібні ваги (інтерпретації)

Вартість: ціна переходу по ребру (наприклад, тариф або витрати ресурсів).
Відстань/час/затримка: довжина дороги, час доставки, latency між вузлами мережі.
Пропускна здатність/надійність/ймовірність: метрики якості з'єднання.

Ключові властивості та нюанси

Довжина шляху - сума ваг ребер (або комбінована сума, якщо враховуються ваги вершин).
Від'ємні ребра допустимі, але наявність від'ємних циклів робить задачу пошуку найкоротшого шляху некоректною (мінімальної довжини не існує).
У задачах мінімального остовного дерева (MST) ваги зазвичай на ребрах; можливі й від'ємні ваги - алгоритми все одно знаходять остов мінімальної сумарної вартості.
Вагу на вершині можна звести до ваг на ребрах, наприклад, розділивши вершину на вхід і вихід з ребром між ними, яке має вагу вершини.

Представлення в пам'яті

Списки суміжності: для кожної вершини зберігається список пар (сусід, вага). Ефективно за пам'яттю для розріджених графів.
Матриця суміжності: квадратна матриця, де комірка i,j - вага ребра i→j, а відсутність ребра кодують спеціальним значенням (наприклад, Infinity). Зручно для щільних графів.

// Приклад: список суміжності з вагами
const graph = {
  A: [{ to: 'B', w: 4 }, { to: 'C', w: 2 }],
  B: [{ to: 'C', w: 5 }, { to: 'D', w: 10 }],
  C: [{ to: 'E', w: 3 }],
  D: [{ to: 'F', w: 11 }],
  E: [{ to: 'D', w: 4 }],
  F: []
};

// Приклад: матриця суміжності (Infinity означає відсутнє ребро)
const V = ['A', 'B', 'C'];
const INF = Infinity;
const M = [
  /*A*/ [0,    7,    2   ],
  /*B*/ [7,    0,    INF ],
  /*C*/ [2,    INF,  0   ]
];

Базові алгоритми для зважених графів

Найкоротші шляхи з однієї вершини: Дейкстра (лише невід'ємні ваги).
Найкоротші шляхи з можливими від'ємними ребрами: Беллмана-Форда; для DAG - динаміка за топологічним порядком (допускає від'ємні ребра, якщо немає циклів).
Усі пари найкоротших шляхів: Флойда-Уоршелла (підходить для невеликих графів, O(V^3)) або Джонсона (ефективніший на розріджених графах).
Евристичний пошук: A* (потрібна допустима евристика, ваги невід'ємні).
Мінімальне остовне дерево: Крускала, Прима (працюють з будь-якими вагами ребер, включно з від'ємними).

Приклад: найкоротший шлях (Дейкстра, JavaScript)

// Важливо: працює лише за невід'ємних ваг
function dijkstra(graph, start) {
  const dist = {};
  const prev = {};
  const visited = new Set();
  for (const v in graph) {
    dist[v] = Infinity;
    prev[v] = null;
  }
  dist[start] = 0;

  // Найпростіша черга з пріоритетом (повільна, але компактна)
  const pq = [{ v: start, d: 0 }];
  function push(node) { pq.push(node); }
  function popMin() {
    let best = 0;
    for (let i = 1; i < pq.length; i++) {
      if (pq[i].d < pq[best].d) best = i;
    }
    return pq.splice(best, 1)[0];
  }

  while (pq.length) {
    const { v: u } = popMin();
    if (visited.has(u)) continue;
    visited.add(u);

    for (const { to, w } of graph[u]) {
      const alt = dist[u] + w;
      if (alt < dist[to]) {
        dist[to] = alt;
        prev[to] = u;
        push({ v: to, d: alt });
      }
    }
  }

  return { dist, prev };
}

function reconstructPath(prev, target) {
  const path = [];
  for (let v = target; v !== null; v = prev[v]) path.push(v);
  return path.reverse();
}

// Приклад використання
const graph = {
  A: [{ to: 'B', w: 4 }, { to: 'C', w: 2 }],
  B: [{ to: 'C', w: 5 }, { to: 'D', w: 10 }],
  C: [{ to: 'E', w: 3 }],
  D: [{ to: 'F', w: 11 }],
  E: [{ to: 'D', w: 4 }],
  F: []
};

const { dist, prev } = dijkstra(graph, 'A');
console.log(dist); // найкоротші відстані від A до решти
console.log(reconstructPath(prev, 'D')); // приклад шляху A -> C -> E -> D

Типові питання на співбесіді

Яке представлення графа оберете і чому? (список суміжності vs матриця)
Який алгоритм для найкоротших шляхів використати за наявності від'ємних ваг? (Беллмана-Форда; перевірка від'ємних циклів)
Що робити, якщо ваги лише 0 або 1? (0-1 BFS з деком)
Чим невзважений граф відрізняється від зваженого? (у невзваженому всі ваги дорівнюють 1, BFS еквівалентний Дейкстрі)

Коротке резюме

Зважений граф - це звичайний граф із додатковою міткою-числом на ребрах або вершинах. Ця мітка задає "ціну" переходу і дозволяє розв'язувати практичні задачі на кшталт пошуку найкоротшого шляху, вибору мінімального остова або оптимального маршруту. Вибір структури даних та алгоритму залежить від властивостей ваг (наявності від'ємних), розміру та щільності графа.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.