Діаметр графа#1796

Діаметр графа (Розбір)

Щоб обчислити діаметр і радіус, нам потрібні найкоротші відстані між усіма парами вершин. Позначимо через $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n вершини графа, а через $d (v_{i}, v_{j})$ d(v_i, v_j) — найкоротшу відстань між вершинами $v_{i}$ v_i та $v_{j}$ v_j. Побудуємо матрицю всіх таких відстаней за допомогою алгоритму Флойда — Воршелла.

Алгоритм Флойда — Воршелла. Спочатку $d (v_{i}, v_{j})$ d(v_i, v_j) дорівнює вазі ребра між вершинами $v_{i}$ v_i та $v_{j}$ v_j, або нескінченності, якщо такого ребра немає; $d (v_{i}, v_{i}) = 0$ d(v_i, v_i) = 0. Потім ми по черзі перебираємо вершини $v_{k}$ v_k і для кожної пари вершин $(v_{i}, v_{j})$ (v_i, v_j) перевіряємо, чи стане шлях коротшим, якщо він проходитиме через вершину $v_{k}$ v_k:

d (v_{i}, v_{j}) = min (d (v_{i}, v_{j}), d (v_{i}, v_{k}) + d (v_{k}, v_{j}))

d(v_i, v_j) = \min(d(v_i, v_j), d(v_i, v_k) + d(v_k, v_j))

Після обробки вершини $v_{k}$ v_k матриця містить довжини найкоротших шляхів, усі проміжні вершини яких лежать серед $v_{1}, \dots, v_{k}$ v_1, \ldots, v_k. Отже, після обробки всіх $n$ вершин матриця міститиме потрібні найкоротші відстані.

Ексцентриситети. Ексцентриситет $r (v_{i})$ r(v_i) вершини $v_{i}$ v_i дорівнює максимальному елементу $i$ -го рядка матриці найкоротших відстаней:

r (v_{i}) = 1 \leq j \leq n max d (v_{i}, v_{j})

r(v_i) = \max_{1 \le j \le n} d(v_i, v_j)

Діаметр графа — це максимальна відстань між парою вершин, тобто максимум серед ексцентриситетів $r (v_{i})$ r(v_i). Радіус графа — це мінімум серед ексцентриситетів $r (v_{i})$ r(v_i).

Приклад

Граф, наведений у прикладі, показано нижче. На лівому рисунку виділено найкоротший шлях, довжина якого дорівнює діаметру, а на правому — вершину, ексцентриситет якої дорівнює радіусу.

Обчислимо найкоротші відстані між усіма парами вершин. Наприклад, між вершинами $2$ і $3$ немає ребра. Шлях $2 \to 4 \to 3$ 2 \to 4 \to 3 має довжину $5 + 4 = 9$ 5 + 4 = 9, тоді як шлях $2 \to 4 \to 1 \to 3$ 2 \to 4 \to 1 \to 3 є коротшим: $5 + 2 + 1 = 8$ 5 + 2 + 1 = 8, тому $d (v_{2}, v_{3}) = 8$ d(v_2, v_3) = 8. Аналогічно, $d (v_{3}, v_{4}) = 3$ d(v_3, v_4) = 3: шлях $3 \to 1 \to 4$ 3 \to 1 \to 4 довжиною $1 + 2 = 3$ 1 + 2 = 3 коротший за пряме ребро вагою $4$ .

Матриця найкоротших відстаней та ексцентриситети вершин мають такий вигляд:

	$1$	$2$	$3$	$4$	$r (v_{i})$ \boldsymbol{r(v_i)}
$1$	$0$	$7$	$1$	$2$	$7$
$2$	$7$	$0$	$8$	$5$	$8$
$3$	$1$	$8$	$0$	$3$	$8$
$4$	$2$	$5$	$3$	$0$	$5$

Максимальний ексцентриситет дорівнює $8$ і досягається у вершинах $2$ та $3$ — це діаметр графа. Мінімальний ексцентриситет дорівнює $5$ і досягається у вершині $4$ — це радіус графа.

Реалізація алгоритму

Оголосимо константи та матрицю ваг графа $g$ . Відсутнє ребро позначається «нескінченністю» $I N F = 0x3F3F3F3F$ INF = \mathrm{0x3F3F3F3F}. Це значення гарантовано більше за довжину будь-якого найкоротшого шляху (яка не перевищує $99 \cdot 1000$ 99 \cdot 1000). Водночас сума двох нескінченностей все ще вміщується в тип $in t$ , тому при обчисленні $g [i] [k] + g [k] [j]$ g[i][k] + g[k][j] переповнення не відбувається.

#define MAX 110
#define INF 0x3F3F3F3F
int g[MAX][MAX];

Функція floyd реалізує алгоритм Флойда — Воршелла. Зовнішній цикл перебирає проміжну вершину $k$ . Для кожної пари вершин $(i, j)$ ми перевіряємо, чи можна скоротити шлях з $i$ до $j$ , проходячи через вершину $k$ . Якщо $g [i] [k] + g [k] [j] < g [i] [j]$ g[i][k] + g[k][j] < g[i][j], ми оновлюємо значення $g [i] [j]$ g[i][j]. Найкоротші відстані обчислюються безпосередньо в матриці $g$ .

void floyd(void)
{
  int i, j, k;
  for(k = 0; k < n; k++)
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if (g[i][k] + g[k][j] < g[i][j])
      g[i][j] = g[i][k] + g[k][j];
}

C++

Основна частина програми. Прочитаємо кількість вершин $n$ та матрицю суміжності графа. Значення $- 1$ означає, що ребра немає; замінимо його на $I N F$ .

scanf("%d",&n);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
  scanf("%d",&g[i][j]);
  if (g[i][j] < 0) g[i][j] = INF;
}

C++

Обчислимо найкоротші відстані між усіма парами вершин. Після виклику $f l oy d$ значення $g [i] [j]$ g[i][j] дорівнюватиме найкоротшій відстані між вершинами $i$ та $j$ .

floyd();

Для кожної вершини $i$ обчислимо її ексцентриситет $ma x$ — максимальний елемент $i$ -го рядка матриці $g$ . Максимум серед усіх ексцентриситетів дорівнює діаметру графа $d iam$ , а мінімум — радіусу графа $r a d i u s$ .

diam = 0; radius = INF;
for(i = 0; i < n; i++)
{
  max = 0;
  for(j = 0; j < n; j++)
    if (g[i][j] > max) max = g[i][j];
  if (max > diam) diam = max;
  if (max < radius) radius = max;
}

C++

Виведемо діаметр і радіус графа.

printf("%d\n%d\n",diam,radius);

Реалізація на Java

import java.util.Scanner;

public class Main
{
  static final int INF = 0x3F3F3F3F;
  static int g[][];
  static int n;

  static void floyd()
  {
    for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if (g[i][k] + g[k][j] < g[i][j])
        g[i][j] = g[i][k] + g[k][j];
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new int[n][n];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
      g[i][j] = con.nextInt();
      if (g[i][j] < 0) g[i][j] = INF;
    }
    floyd();
    int diam = 0, radius = INF;
    for(int i = 0; i < n; i++)
    {
      int max = 0;
      for(int j = 0; j < n; j++)
        if (g[i][j] > max) max = g[i][j];
      if (max > diam) diam = max;
      if (max < radius) radius = max;
    }

    System.out.println(diam + "\n" + radius);
    con.close();
  }
}

Java