Diámetro del grafo#1796

Diámetro del grafo (Editorial)

Para calcular el diámetro y el radio, necesitamos las distancias más cortas entre todos los pares de vértices. Denotemos por $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n los vértices del grafo, y por $d (v_{i}, v_{j})$ d(v_i, v_j) la distancia más corta entre los vértices $v_{i}$ v_i y $v_{j}$ v_j. Construimos la matriz de todas estas distancias usando el algoritmo de Floyd — Warshall.

Algoritmo de Floyd — Warshall. Inicialmente, $d (v_{i}, v_{j})$ d(v_i, v_j) es igual al peso de la arista entre los vértices $v_{i}$ v_i y $v_{j}$ v_j, o infinito si no existe tal arista; $d (v_{i}, v_{i}) = 0$ d(v_i, v_i) = 0. Luego iteramos sobre los vértices $v_{k}$ v_k uno por uno y, para cada par de vértices $(v_{i}, v_{j})$ (v_i, v_j), verificamos si el camino se acorta al pasar por el vértice $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))

Después de procesar el vértice $v_{k}$ v_k, la matriz contiene las longitudes de los caminos más cortos cuyos vértices intermedios se encuentran todos entre $v_{1}, \dots, v_{k}$ v_1, \ldots, v_k. Por lo tanto, después de procesar los $n$ vértices, la matriz contiene las distancias más cortas requeridas.

Excentricidades. La excentricidad $r (v_{i})$ r(v_i) del vértice $v_{i}$ v_i es igual al elemento máximo de la $i$ -ésima fila de la matriz de distancias más cortas:

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)

El diámetro del grafo es la distancia máxima entre un par de vértices, es decir, el máximo de las excentricidades $r (v_{i})$ r(v_i). El radio del grafo es el mínimo de las excentricidades $r (v_{i})$ r(v_i).

Ejemplo

El grafo dado en el ejemplo se muestra a continuación. La figura de la izquierda resalta el camino más corto cuya longitud es igual al diámetro, y la figura de la derecha resalta el vértice cuya excentricidad es igual al radio.

Calculemos las distancias más cortas entre todos los pares de vértices. Por ejemplo, no hay arista entre los vértices $2$ y $3$ . El camino $2 \to 4 \to 3$ 2 \to 4 \to 3 tiene longitud $5 + 4 = 9$ 5 + 4 = 9, mientras que el camino $2 \to 4 \to 1 \to 3$ 2 \to 4 \to 1 \to 3 es más corto: $5 + 2 + 1 = 8$ 5 + 2 + 1 = 8, por lo que $d (v_{2}, v_{3}) = 8$ d(v_2, v_3) = 8. De manera similar, $d (v_{3}, v_{4}) = 3$ d(v_3, v_4) = 3: el camino $3 \to 1 \to 4$ 3 \to 1 \to 4 de longitud $1 + 2 = 3$ 1 + 2 = 3 es más corto que la arista directa de peso $4$ .

La matriz de distancias más cortas y las excentricidades de los vértices son las siguientes:

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

La excentricidad máxima es igual a $8$ y se alcanza en los vértices $2$ y $3$ — este es el diámetro del grafo. La excentricidad mínima es igual a $5$ y se alcanza en el vértice $4$ — este es el radio del grafo.

Implementación del algoritmo

Declaramos las constantes y la matriz de pesos del grafo $g$ . Una arista ausente se denota con "infinito" $I N F = 0x3F3F3F3F$ INF = \mathrm{0x3F3F3F3F}. Este valor es ciertamente mayor que la longitud de cualquier camino más corto (que no excede $99 \cdot 1000$ 99 \cdot 1000). Al mismo tiempo, la suma de dos infinitos todavía cabe en el tipo $in t$ , por lo que no se produce desbordamiento al calcular $g [i] [k] + g [k] [j]$ g[i][k] + g[k][j].

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

La función floyd implementa el algoritmo de Floyd — Warshall. El bucle externo itera sobre el vértice intermedio $k$ . Para cada par de vértices $(i, j)$ , verificamos si el camino de $i$ a $j$ puede acortarse al pasar por el vértice $k$ . Si $g [i] [k] + g [k] [j] < g [i] [j]$ g[i][k] + g[k][j] < g[i][j], actualizamos el valor $g [i] [j]$ g[i][j]. Las distancias más cortas se calculan directamente en la matriz $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 principal del programa. Leemos el número de vértices $n$ y la matriz de adyacencia del grafo. El valor $- 1$ significa que no hay arista; lo reemplazamos por $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++

Calculamos las distancias más cortas entre todos los pares de vértices. Después de llamar a $f l oy d$ , el valor $g [i] [j]$ g[i][j] es igual a la distancia más corta entre los vértices $i$ y $j$ .

floyd();

Para cada vértice $i$ , calculamos su excentricidad $ma x$ — el elemento máximo de la $i$ -ésima fila de la matriz $g$ . El máximo de todas las excentricidades es igual al diámetro del grafo $d iam$ , y el mínimo es igual al radio 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++

Imprimimos el diámetro y el radio del grafo.

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

Implementación en 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