Diametro del grafo#1796

Diametro del grafo (Editoriale)

Per calcolare il diametro e il raggio, abbiamo bisogno delle distanze minime tra tutte le coppie di vertici. Indichiamo con $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n i vertici del grafo, e con $d (v_{i}, v_{j})$ d(v_i, v_j) la distanza minima tra i vertici $v_{i}$ v_i e $v_{j}$ v_j. Costruiamo la matrice di tutte queste distanze utilizzando l'algoritmo di Floyd — Warshall.

Algoritmo di Floyd — Warshall. Inizialmente, $d (v_{i}, v_{j})$ d(v_i, v_j) è uguale al peso dell'arco tra i vertici $v_{i}$ v_i e $v_{j}$ v_j, oppure infinito se tale arco non esiste; $d (v_{i}, v_{i}) = 0$ d(v_i, v_i) = 0. Poi iteriamo sui vertici $v_{k}$ v_k uno per uno e, per ogni coppia di vertici $(v_{i}, v_{j})$ (v_i, v_j), verifichiamo se il percorso diventa più corto passando per il vertice $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))

Dopo aver elaborato il vertice $v_{k}$ v_k, la matrice contiene le lunghezze dei cammini minimi i cui vertici intermedi si trovano tutti tra $v_{1}, \dots, v_{k}$ v_1, \ldots, v_k. Pertanto, dopo aver elaborato tutti gli $n$ vertici, la matrice contiene le distanze minime richieste.

Eccentricità. L'eccentricità $r (v_{i})$ r(v_i) del vertice $v_{i}$ v_i è uguale all'elemento massimo della $i$ -esima riga della matrice delle distanze minime:

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)

Il diametro del grafo è la distanza massima tra una coppia di vertici, ossia il massimo delle eccentricità $r (v_{i})$ r(v_i). Il raggio del grafo è il minimo delle eccentricità $r (v_{i})$ r(v_i).

Esempio

Il grafo dato nell'esempio è mostrato di seguito. La figura a sinistra evidenzia il cammino minimo la cui lunghezza è uguale al diametro, mentre la figura a destra evidenzia il vertice la cui eccentricità è uguale al raggio.

Calcoliamo le distanze minime tra tutte le coppie di vertici. Ad esempio, non c'è nessun arco tra i vertici $2$ e $3$ . Il percorso $2 \to 4 \to 3$ 2 \to 4 \to 3 ha lunghezza $5 + 4 = 9$ 5 + 4 = 9, mentre il percorso $2 \to 4 \to 1 \to 3$ 2 \to 4 \to 1 \to 3 è più corto: $5 + 2 + 1 = 8$ 5 + 2 + 1 = 8, quindi $d (v_{2}, v_{3}) = 8$ d(v_2, v_3) = 8. Analogamente, $d (v_{3}, v_{4}) = 3$ d(v_3, v_4) = 3: il percorso $3 \to 1 \to 4$ 3 \to 1 \to 4 di lunghezza $1 + 2 = 3$ 1 + 2 = 3 è più corto dell'arco diretto di peso $4$ .

La matrice delle distanze minime e le eccentricità dei vertici sono le seguenti:

	$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$

L'eccentricità massima è uguale a $8$ ed è raggiunta nei vertici $2$ e $3$ — questo è il diametro del grafo. L'eccentricità minima è uguale a $5$ ed è raggiunta nel vertice $4$ — questo è il raggio del grafo.

Implementazione dell'algoritmo

Dichiariamo le costanti e la matrice dei pesi del grafo $g$ . Un arco mancante è indicato con "infinito" $I N F = 0x3F3F3F3F$ INF = \mathrm{0x3F3F3F3F}. Questo valore è sicuramente maggiore della lunghezza di qualsiasi cammino minimo (che non supera $99 \cdot 1000$ 99 \cdot 1000). Allo stesso tempo, la somma di due infiniti rientra comunque nel tipo $in t$ , quindi non si verifica overflow nel calcolo di $g [i] [k] + g [k] [j]$ g[i][k] + g[k][j].

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

La funzione floyd implementa l'algoritmo di Floyd — Warshall. Il ciclo esterno itera sul vertice intermedio $k$ . Per ogni coppia di vertici $(i, j)$ , verifichiamo se il percorso da $i$ a $j$ può essere accorciato passando per il vertice $k$ . Se $g [i] [k] + g [k] [j] < g [i] [j]$ g[i][k] + g[k][j] < g[i][j], aggiorniamo il valore $g [i] [j]$ g[i][j]. Le distanze minime vengono calcolate direttamente nella matrice $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++

La parte principale del programma. Leggiamo il numero di vertici $n$ e la matrice di adiacenza del grafo. Il valore $- 1$ significa che non c'è nessun arco; lo sostituiamo con $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++

Calcoliamo le distanze minime tra tutte le coppie di vertici. Dopo la chiamata a $f l oy d$ , il valore $g [i] [j]$ g[i][j] è uguale alla distanza minima tra i vertici $i$ e $j$ .

floyd();

Per ogni vertice $i$ , calcoliamo la sua eccentricità $ma x$ — l'elemento massimo della $i$ -esima riga della matrice $g$ . Il massimo di tutte le eccentricità è uguale al diametro del grafo $d iam$ , e il minimo è uguale al raggio del grafo $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++

Stampiamo il diametro e il raggio del grafo.

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

Implementazione in 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