Longest path in a tree (Editorial)

The shortest path in a weighted tree can be found using either depth-first search or breadth-first search; using Dijkstra’s algorithm is not necessary in this case.

To find the longest path (the diameter of the tree), proceed as follows:

1. Perform a breadth-first search starting from the first vertex. Identify the vertex $v$, which has the longest path from the starting vertex.

2. Next, perform a breadth-first search starting from vertex $v$ to find the vertex u, which also has the longest path from $v$.

3. The path from $v$ to $u$ is the longest path in the tree (the tree's diameter).

Example

The tree shown in the example has the following structure:

• Perform a breadth-first search starting from vertex $1$ (left picture). The longest path will be to vertex $4$.

• Then, perform a breadth-first search starting from vertex $4$ (right picture). The longest path will be to vertex $3$, and its length is $12$.

Algorithm implementation

Declare the adjacency list of the graph $g$.

Declare the array of shortest distances $d$.

vector<vector<pair<int, int>> > g;
vector<long long> d;

The function bfs performs a breadth-first search starting from vertex $v$.

int bfs(int v)
{
  deque<int> q;
  q.push_back(v);
  while (!q.empty())
  {
    int v = q.front(); q.pop_front();
    for (auto x : g[v])
    {
      int to = x.first;
      int w = x.second;
      if (d[to] == -1)
      {
        d[to] = d[v] + w;
        q.push_back(to);
      }
    }
  }

Return the number of the vertex to which the distance from vertex $v$ is maximal.

  return max_element(d.begin() + 1, d.begin() + n + 1) - d.begin();
}

The main part of the program. Read the input data. Build the graph.

scanf("%d", &n);
g.resize(n + 1);

for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %lld", &b, &e, &dist);
  g[b].push_back({ e, dist });
  g[e].push_back({ b, dist });
}

Initialize the array of shortest distances.

d = vector<long long>(n + 1, -1);
d[1] = 0;

Perform the first breadth-first search starting from vertex $1$. Identify the vertex $v$ that is farthest from vertex $1$.

int v = bfs(1);

Re-initialize the array of shortest distances and perform the second breadth-first search starting from vertex $v$.

d = vector<long long>(n + 1, -1);
d[v] = 0;
v = bfs(v);

Print the result — the length of the longest path.

printf("%lld\n", d[v]);

Algorithm implementation — depth first serch

The adjacency list of the graph is stored in the array $g$.

To store the shortest distances, declare the array $dist$.

vector<vector<pair<int, int>> > g;
vector<long long> dist;

The function dfs performs a depth-first search starting from vertex $v$. Vertex $p$ is the parent of $v$ during the depth-first search.

void dfs(int v, int p = -1)
{

Iterate over all edges adjacent to vertex $v$.

  for (auto x : g[v])
  {

Consider the edge v → to with weight $w$.

    int to = x.first;
    int w = x.second;

If to \ne p, update dist[to] and perform a depth-first search starting from vertex $to$.

    if (to != p)
    {
      dist[to] = dist[v] + w;
      dfs(to, v);
    }
  }
}

The main part of the program. Read the input data. Build the graph.

scanf("%d", &n);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &b, &e, &w);
  g[b].push_back({ e, w });
  g[e].push_back({ b, w });
}

Perform a depth-first search starting from vertex $1$. Fill the array of shortest distances $dist$ from vertex $1$.

dist.assign(n + 1, -1);
dist[1] = 0;
dfs(1);

Find vertex $v$, which is the farthest from vertex $1$.

v = max_element(dist.begin(), dist.end()) - dist.begin();

Perform a second depth-first search starting from vertex $v$. Fill the array of shortest distances $dist$ from vertex $v$.

dist.assign(n + 1, -1);
dist[v] = 0;
dfs(v);

The largest value in the array $dist$ is equal to the diameter of the tree.

v = max_element(dist.begin(), dist.end()) - dist.begin();

Print the answer.

printf("%lld\n", dist[v]);

Python implementation

from collections import deque

Read the input data. Store the adjacency list of the graph in $g$.

Declare a list of shortest distances $d$.

n = int(input())
g = [[] for _ in range(n + 1)]
d = [-1] * (n + 1)

Construct a graph.

for _ in range(n - 1):
  b, e, dist = map(int, input().split())
  g[b].append((e, dist))
  g[e].append((b, dist))

The function bfs performs a breadth-first search starting from vertex $v$.

def bfs(v):
  q = deque()
  q.append(v)

  while q:
    v = q.popleft()
    for to, w in g[v]:
      if d[to] == -1:
        d[to] = d[v] + w
        q.append(to)

Return the number of the vertex that is farthest from vertex $v$.

  return d.index(max(d))

Perform the first breadth-first search from vertex $1$. Determine the vertex $v$ that is the farthest from vertex $1$.

d[1] = 0
v = bfs(1)

Initialize the array of shortest distances and perform the second breadth-first search from vertex $v$.

d = [-1] * (n + 1)
d[v] = 0
v = bfs(v)

Print the answer — the length of the longest path.

print(d[v])