Introduction

The diameter of a graph is the largest shortest-path distance between any pair of vertices. That sounds like one problem, but the right algorithm depends heavily on the graph class: trees have a very fast exact method, while general graphs often need repeated shortest-path searches, and disconnected graphs force you to define what “diameter” should even mean.

Start with the Definition

For a connected graph, the diameter is the maximum over all pairwise shortest-path distances. In other words, you are not looking for the longest path in the graph. You are looking for the longest among the shortest possible routes.

That distinction matters because longest-path problems are hard in general graphs, while shortest-path problems are well studied and often efficient.

Tree Diameter: Two BFS Runs

For an unweighted tree, the classic exact algorithm is extremely simple:

1. run BFS from any node to find a farthest node u
2. run BFS again from u to find the farthest distance

That second farthest distance is the tree diameter.

1from collections import deque
2
3def bfs_farthest(adj, start):
4    q = deque([start])
5    dist = {start: 0}
6
7    while q:
8        u = q.popleft()
9        for v in adj[u]:
10            if v not in dist:
11                dist[v] = dist[u] + 1
12                q.append(v)
13
14    farthest = max(dist, key=dist.get)
15    return farthest, dist[farthest]
16
17adj = {
18    0: [1],
19    1: [0, 2, 3],
20    2: [1],
21    3: [1, 4],
22    4: [3],
23}
24
25u, _ = bfs_farthest(adj, 0)
26v, diameter = bfs_farthest(adj, u)
27print(u, v, diameter)

For trees, this runs in linear time relative to vertices plus edges, which is why it is the standard answer.

General Unweighted Graphs

For a general unweighted graph, the two-BFS trick is no longer guaranteed to be exact. The safe exact approach is to run BFS from every vertex and keep the largest shortest-path distance you find.

1from collections import deque
2
3def bfs_distances(adj, start):
4    q = deque([start])
5    dist = {start: 0}
6
7    while q:
8        u = q.popleft()
9        for v in adj[u]:
10            if v not in dist:
11                dist[v] = dist[u] + 1
12                q.append(v)
13
14    return dist
15
16def graph_diameter(adj):
17    diameter = 0
18    for node in adj:
19        dist = bfs_distances(adj, node)
20        if len(dist) != len(adj):
21            raise ValueError("graph is disconnected")
22        diameter = max(diameter, max(dist.values()))
23    return diameter

This is exact, but it can be expensive for large graphs because it repeats BFS from every vertex.

Weighted Graphs Need Dijkstra

If the graph has non-negative edge weights, edge count is no longer the right notion of distance. Replace BFS with Dijkstra's algorithm.

1import heapq
2
3def dijkstra(adj, start):
4    dist = {start: 0}
5    heap = [(0, start)]
6
7    while heap:
8        d, u = heapq.heappop(heap)
9        if d != dist[u]:
10            continue
11        for v, w in adj[u]:
12            nd = d + w
13            if v not in dist or nd < dist[v]:
14                dist[v] = nd
15                heapq.heappush(heap, (nd, v))
16    return dist

The overall definition of diameter stays the same. Only the shortest-path subroutine changes.

For dense weighted graphs, all-pairs shortest-path algorithms such as Floyd-Warshall are another option, but they are usually chosen for problem size or representation reasons, not because they are conceptually simpler.

Complexity Depends on Structure

Algorithm choice should follow the graph structure, not habit.

For an unweighted graph with V vertices and E edges:

• one BFS costs O(V + E)
• repeated BFS from every vertex costs O(V * (V + E))

That may be fine for a small sparse graph and completely impractical for a very large network. This is why the first question should be whether the input is a tree, a sparse general graph, a dense graph, or a weighted graph.

Disconnected Graphs Need a Policy

Diameter is usually defined for connected graphs. If the graph is disconnected, you have to decide what your program should mean.

Common choices are:

• treat the diameter as undefined
• compute the diameter of each connected component separately
• use infinity in a theoretical context

Whatever you choose, make it explicit in the code. Quietly returning a number for a disconnected graph often hides a bug rather than solving the problem.

Approximation Is a Different Problem

On very large graphs, exact diameter computation may be too expensive. In those cases, teams often estimate the diameter using repeated BFS or Dijkstra from a limited set of seed nodes. That can be useful, but it is not the same as an exact answer.

If you ship an approximation, document it honestly. “Fast estimate” and “exact diameter” are different guarantees.

Common Pitfalls

• Confusing graph diameter with the longest simple path.
• Applying the two-BFS tree algorithm to arbitrary graphs and assuming it stays exact.
• Using BFS on weighted graphs where Dijkstra is required.
• Ignoring disconnected components and returning a misleading value.
• Calling an estimate the exact diameter without saying so.

Summary

• Diameter is the maximum shortest-path distance between vertices.
• Trees have a fast exact two-BFS solution.
• General unweighted graphs need repeated BFS for an exact result.
• Weighted graphs require a weighted shortest-path algorithm such as Dijkstra.
• Decide explicitly how disconnected graphs should be handled before implementing the algorithm.