8.21

Idea. Compute every shortest path once (Floyd–Warshall), then close each directed edge into a cycle.

Algorithm.
let INF = 10100
input G with n vertices 1..n and positive weights w(u,v)

# 1. all-pairs shortest paths (Floyd–Warshall) --------------
dist[i][j] = w(i,j) if edge (i→j) exists else INF
for i in 1..n: dist[i][i] = 0
for k in 1..n:
  for i in 1..n:
    for j in 1..n:
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

# 2. best cycle length --------------------------------------
ans = INF
for each edge (u→v) of weight w:
  if dist[v][u] < INF: # there is a path v → u
    ans = min(ans, dist[v][u] + w)

return ans # ∞ if acyclic

Correctness. After the first phase dist[v][u] is the length of the shortest path from v to u. Appending edge u→v forms a directed cycle whose length is exactly dist[v][u] + w(u,v). Every simple directed cycle has some last edge; the algorithm evaluates that edge and therefore examines every cycle’s length, returning the minimum.

Complexity. Floyd–Warshall takes [math]O(n^3)[/math]. The final pass over all [math]m\le n^2[/math] edges is [math]O(n^2)[/math]. Hence the overall running time is [math]O(n^3)[/math], meeting the requirement; memory usage is [math]O(n^2)[/math].

Back to Chapter 8