Diameter of the graph#1796

Diameter of the graph (Editorial)

To compute the diameter and the radius, we need the shortest distances between all pairs of vertices. Denote by $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n the vertices of the graph, and by $d (v_{i}, v_{j})$ d(v_i, v_j) the shortest distance between the vertices $v_{i}$ v_i and $v_{j}$ v_j. We build the matrix of all such distances using the Floyd — Warshall algorithm.

Floyd — Warshall algorithm. Initially, $d (v_{i}, v_{j})$ d(v_i, v_j) equals the weight of the edge between the vertices $v_{i}$ v_i and $v_{j}$ v_j, or infinity if there is no such edge; $d (v_{i}, v_{i}) = 0$ d(v_i, v_i) = 0. Then we iterate over the vertices $v_{k}$ v_k one by one and, for each pair of vertices $(v_{i}, v_{j})$ (v_i, v_j), check whether the path becomes shorter if it passes through the vertex $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))

After processing the vertex $v_{k}$ v_k, the matrix contains the lengths of the shortest paths whose intermediate vertices all lie among $v_{1}, \dots, v_{k}$ v_1, \ldots, v_k. Therefore, after all $n$ vertices have been processed, the matrix contains the required shortest distances.

Eccentricities. The eccentricity $r (v_{i})$ r(v_i) of the vertex $v_{i}$ v_i equals the maximum element of the $i$ -th row of the shortest distance matrix:

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)

The diameter of the graph is the maximum distance between a pair of vertices, that is, the maximum of the eccentricities $r (v_{i})$ r(v_i). The radius of the graph is the minimum of the eccentricities $r (v_{i})$ r(v_i).

Example

The graph given in the example is shown below. The left figure highlights the shortest path whose length equals the diameter, and the right figure highlights the vertex whose eccentricity equals the radius.

Let us compute the shortest distances between all pairs of vertices. For example, there is no edge between the vertices $2$ and $3$ . The path $2 \to 4 \to 3$ 2 \to 4 \to 3 has length $5 + 4 = 9$ 5 + 4 = 9, while the path $2 \to 4 \to 1 \to 3$ 2 \to 4 \to 1 \to 3 is shorter: $5 + 2 + 1 = 8$ 5 + 2 + 1 = 8, so $d (v_{2}, v_{3}) = 8$ d(v_2, v_3) = 8. Similarly, $d (v_{3}, v_{4}) = 3$ d(v_3, v_4) = 3: the path $3 \to 1 \to 4$ 3 \to 1 \to 4 of length $1 + 2 = 3$ 1 + 2 = 3 is shorter than the direct edge of weight $4$ .

The shortest distance matrix and the eccentricities of the vertices are as follows:

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

The maximum eccentricity equals $8$ and is reached at the vertices $2$ and $3$ — this is the diameter of the graph. The minimum eccentricity equals $5$ and is reached at the vertex $4$ — this is the radius of the graph.

Algorithm implementation

Declare the constants and the weight matrix of the graph $g$ . A missing edge is denoted by "infinity" $I N F = 0x3F3F3F3F$ INF = \mathrm{0x3F3F3F3F}. This value is certainly greater than the length of any shortest path (which does not exceed $99 \cdot 1000$ 99 \cdot 1000). At the same time, the sum of two infinities still fits into the $in t$ type, so no overflow occurs when computing $g [i] [k] + g [k] [j]$ g[i][k] + g[k][j].

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

The function floyd implements the Floyd — Warshall algorithm. The outer loop iterates over the intermediate vertex $k$ . For each pair of vertices $(i, j)$ , we check whether the path from $i$ to $j$ can be shortened by passing through the vertex $k$ . If $g [i] [k] + g [k] [j] < g [i] [j]$ g[i][k] + g[k][j] < g[i][j], we update the value $g [i] [j]$ g[i][j]. The shortest distances are computed directly in the matrix $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++

The main part of the program. Read the number of vertices $n$ and the adjacency matrix of the graph. The value $- 1$ means that there is no edge; replace it with $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++

Compute the shortest distances between all pairs of vertices. After the call to $f l oy d$ , the value $g [i] [j]$ g[i][j] equals the shortest distance between the vertices $i$ and $j$ .

floyd();

For each vertex $i$ , compute its eccentricity $ma x$ — the maximum element of the $i$ -th row of the matrix $g$ . The maximum of all eccentricities equals the diameter of the graph $d iam$ , and the minimum equals the radius of the graph $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++

Print the diameter and the radius of the graph.

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

Java implementation

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