AIOJ

Introduction

Problem

Given a graph, determine the minimum possible total edge weight of a cycle consisting of $n$ vertices $(n\ge 3)$ .

The minimum cycle of a graph is also called its girth.

Method

Brute-force Solution

Suppose $u$ and $v$ are joined by an edge of length $w$ . Let $dis(u,v)$ denote the shortest path between $u$ and $v$ after removing the edge between $u$ and $v$ .

Then the minimum cycle in an undirected graph is $dis(u,v)+w$ .

For a directed graph, the corresponding formula must be changed: the minimum cycle is $dis(v,u)+w$ .

The total time complexity is $O(n^2m)$ .

Dijkstra

Process

Enumerate all edges; for each edge, remove it and run Dijkstra from its starting vertex. The reasoning is the same as above.

Property

The time complexity is $O(m(n+m)\log n)$ .

Floyd

Process

For vertices $u,v$ in the original graph, let the edge weight be $val\left(u,v\right)$ .

The Floyd algorithm has the following property: when the outer loop reaches vertex $k$ (before the $k$ -th iteration begins), the shortest-path array $dis$ has an entry $dis_{u,v}$ representing the shortest path from $u$ to $v$ that only passes through vertices whose indices lie in $\left[1, k\right)$ .

By the definition of a minimum cycle, it has at least three vertices. Let $w$ be the vertex on the cycle with the largest index, and let the two vertices adjacent to $w$ on the cycle be $u,v$ . When the outer loop reaches $k=w$ , the cycle length is $dis_{u,v}+val\left(v,w\right)+val\left(w,u\right)$ .

Therefore, during the loop, for each $k$ , enumerate the pairs satisfying $i<k,j<k$ , namely $(i,j)$ , and update the answer.

Recording Paths

We now know that the cycle has the form $u\to k\to v$ , followed by a path from $v$ back to $u$ (all intermediate vertex indices are $<k$ ).

The problem becomes finding a path from $v\leadsto u$ . By the triangle inequality $dis_{u,v}\le dis_{u,i}+dis_{i,v}$ , record $pos_{u,v}=j$ for a vertex satisfying $dis_{u,v}=dis_{u,j}+dis_{j,v}$ . Clearly, $j$ lies on the $v\leadsto u$ path.

We can therefore split the path into $v\leadsto j$ and $j\leadsto u$ , and process the two parts recursively.

Proof That the Recursion Does Not Loop Forever

We use a proof by contradiction.

Suppose the cycle passes through a vertex $u$ more than once. Then the cycle must contain a segment that starts at $u$ , follows several edges, and returns to $u$ . This segment forms a new cycle.

Since the graph has no negative cycle (otherwise there would be no minimum cycle), the total edge weight of the new cycle is no greater than that of the original cycle.

We can therefore keep only this cycle, which does not pass through any vertex $u$ more than once. This contradicts the assumption, so the cycle cannot repeat a vertex.

Thus, when the recursion reaches vertices $u,v$ , $pos_{u,v}$ cannot be either vertex index; a new vertex must have been added.

In particular, return directly when $u$ and $v$ are adjacent.

Since the total number of vertices is $n$ , the number of additions (that is, the recursion depth) cannot exceed $n$ , so the recursion cannot loop forever.

Property

The time complexity is $O(n^3)$ .

Implementation

The following are reference implementations in C++ and Python (with path reconstruction):

C++

// The number of vertices is n
int val[MAXN + 1][MAXN + 1];  // Adjacency matrix of the original graph
int cnt, path[MAXN + 5];      // Record the path and length of the minimum cycle

void get_path(int u, int v) {  // Obtain the path from u to v
  if (pos[u][v] == 0) return;

  int k = pos[u][v];
  get_path(u, k);
  path[++cnt] = k;
  get_path(k, v);
}

void Floyd(const int &n) {
  static int dis[MAXN + 1][MAXN + 1];  // Shortest-path matrix
  static int pos[MAXN + 1][MAXN + 1];
  memcpy(dis, val, sizeof(val));
  memset(pos, 0, sizeof(pos));
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        if (ans >
            (long long)val[i][k] + val[k][j] + dis[i][j]) {  // A shorter cycle was found
          // Here, we ensure that j dis[i][k] + dis[k][j]) {
          dis[i][j] = dis[i][k] + dis[k][j];
          pos[i][j] = k;  // The current path can be updated through k
        }
      }
  }
}

Python

# Define a sufficiently large value to represent infinity
INF = sys.maxsize

def get_path(i, j, pos, path, cnt):
    """
    Recursively collect the intermediate vertices on a shortest path from vertex i to vertex j.

    Args:
        i (int): start vertex (0-based index).
        j (int): end vertex (0-based index).
        pos (list[list[int]]): matrix recording shortest-path intermediate vertices. pos[i][j] = k means that the shortest path from i to j passes through k.
        path (list[int]): list storing path vertices (using 0-based indices).
        cnt (int): current number of vertices in the path.

    Returns:
        int: updated number of vertices in the path.
    """
    # If pos[i][j] is -1, there is no intermediate vertex from i to j
    if pos[i][j] == -1:
        return cnt

    # Get the intermediate vertex k
    k = pos[i][j]
    # Recursively obtain the path from i to k
    cnt = get_path(i, k, pos, path, cnt)
    # Add the intermediate vertex k to the path
    path[cnt] = k
    cnt += 1
    # Recursively obtain the path from k to j
    cnt = get_path(k, j, pos, path, cnt)
    return cnt

def find_minimum_cycle_undirected(n, edges):
    """
    Find a minimum cycle in an undirected graph using the Floyd-Warshall algorithm.

    Args:
        n (int): number of graph vertices (1 through n).
        edges (list[tuple]): list of edges; each element (u, v, w) represents an edge of weight w between vertices u and v.
                             Vertex indices range from 1 to n.

    Returns:
        tuple: the minimum-cycle length and its path.
               Return (INF, []) if no cycle exists.
               The path is a list of vertex indices (1-based).
    """
    # Use 0-based indexing internally
    N = n
    # Initialize adjacency matrix g with the original edge weights
    g = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize shortest-path matrix dis, initially equal to g
    dis = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize matrix pos to record intermediate vertices on shortest paths
    pos = [[-1 for _ in range(N)] for _ in range(N)]

    # Initialize the diagonal to 0 (the distance from a vertex to itself)
    for i in range(N):
        g[i][i] = 0
        dis[i][i] = 0

    # Build the adjacency matrix from the input edges (undirected graph)
    for u, v, w in edges:
        # Convert 1-based indices to 0-based
        u -= 1
        v -= 1
        # For an undirected graph, edges are bidirectional
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
        dis[u][v] = min(dis[u][v], w)
        dis[v][u] = min(dis[v][u], w)

    # Initialize the minimum cycle length to infinity
    min_cycle_len = INF
    # Initialize the minimum-cycle path
    min_cycle_path = []

    # Core of the Floyd-Warshall algorithm
    # k is the intermediate vertex (0-based index)
    for k in range(N):
        # Before updating dis[i][j], check whether passing through k forms a shorter cycle
        # The cycle is i -> k -> j -> ... -> i
        # Here dis[i][j] is the shortest path considering vertices 0 through k-1 as intermediate vertices
        # The C++ code loops with i < k and j < i; we follow the same logic here (0-based)
        for i in range(k):  # 0 <= i < k
            for j in range(i):  # 0 <= j < i
                # Check whether i, k, and j form a cycle connected by dis[i][j]
                # Ensure that the original edges g[i][k] and g[k][j] exist (are not INF)
                # Also ensure that the shortest path dis[i][j] from i to j exists (is not INF)
                if g[i][k] != INF and g[k][j] != INF and dis[i][j] != INF:
                    current_cycle_len = g[i][k] + g[k][j] + dis[i][j]
                    if current_cycle_len < min_cycle_len:
                        min_cycle_len = current_cycle_len
                        # Reconstruct the path
                        path = [0] * (N + 5)  # Temporarily store the path in an array large enough
                        cnt = 0
                        # Add vertices to the path in the order i, k, j
                        path[cnt] = i
                        cnt += 1
                        path[cnt] = k
                        cnt += 1
                        path[cnt] = j
                        cnt += 1
                        # Get the intermediate vertices on the shortest path from j to i (using the previously computed dis and pos)
                        cnt = get_path(j, i, pos, path, cnt)
                        # Extract the actual path vertices (remove unused entries)
                        # Convert 0-based indices to 1-based
                        min_cycle_path = [node + 1 for node in path[:cnt]]

        # Standard Floyd-Warshall shortest-path update
        for i in range(N):
            for j in range(N):
                if (
                    dis[i][k] != INF
                    and dis[k][j] != INF
                    and dis[i][j] > dis[i][k] + dis[k][j]
                ):
                    dis[i][j] = dis[i][k] + dis[k][j]
                    # Record that the shortest path from i to j passes through k
                    pos[i][j] = k

    return min_cycle_len, min_cycle_path

Template Problem

AcWing 344 Tourist Attraction

Given an undirected graph with $n$ vertices, find a cycle containing at least $3$ distinct vertices whose total edge weight is minimum.

This is called the minimum-cycle problem for an undirected graph.

You must output one minimum-cycle solution; if the minimum cycle is not unique, any one is acceptable.

$n \le 100$

An $O(n^3)$ solution is acceptable; apply the Floyd-based minimum-cycle method.

C++

#include <bits/stdc++.h>
using lint = long long;
// Define a sufficiently large constant for the maximum number of vertices
const int MAXN = 110;

// Define a sufficiently large value for infinity and initialize the minimum-cycle length
lint ans = 1e9;  // lint is an alias for long long

// The graph has n vertices and m edges
// cnt records the number of vertices in the minimum-cycle path
// path stores the vertices of the minimum-cycle path
int n, m, cnt, path[MAXN];

// g stores the adjacency matrix of the original graph
// dis stores the shortest-path matrix (updated during Floyd-Warshall)
// pos records intermediate vertices on shortest paths; pos[i][j] = k means the shortest path from i to j passes through k
int g[MAXN][MAXN], dis[MAXN][MAXN], pos[MAXN][MAXN];

// Recursive function: obtain intermediate vertices on the shortest path from u to v
// Reconstruct the path from matrix pos
void get_path(int u, int v) {
  // If pos[u][v] is 0, there is no intermediate vertex from u to v; return directly
  if (pos[u][v] == 0) return;

  // Get the intermediate vertex k
  int k = pos[u][v];
  // Recursively obtain the path from u to k
  get_path(u, k);
  // Add the intermediate vertex k to the path
  path[++cnt] = k;
  // Recursively obtain the path from k to v
  get_path(k, v);
}

// Floyd-Warshall function: find a minimum cycle in the graph
void Floyd() {
  // Outer loop: k is the intermediate vertex (1 to n)
  for (int k = 1; k <= n; ++k) {
    // Inner loops: i and j, checking whether a shorter cycle can pass through k
    // Here i runs from 1 to k-1 and j from 1 to i-1
    // This checks cycles of the form i -> k -> j -> ... -> i
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        // Check whether connecting i and j through k forms a shorter cycle
        // The cycle length is the original edge weight g[i][k] from i to k plus the original edge weight g[k][j] from k to j
        // + the current shortest path dis[i][j] from i to j
        if (ans > (long long)g[i][k] + g[k][j] + dis[i][j]) {
          // A shorter cycle was found
          ans = g[i][k] + g[k][j] + dis[i][j];  // Update the minimum-cycle length
          cnt = 0;                              // Reset the path count
          // Add i, k, and j to the path in order
          path[++cnt] = i, path[++cnt] = k, path[++cnt] = j;
          // Get the intermediate vertices on the shortest path from j to i and add them to the path
          get_path(j, i);
        }

    // Standard Floyd-Warshall shortest-path update
    // i from 1 to n, j from 1 to n
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) {
        // If a shorter path from i to j can be obtained through intermediate vertex k
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          // Update the shortest path
          dis[i][j] = dis[i][k] + dis[k][j];
          // Record that the shortest path from i to j passes through k
          pos[i][j] = k;
        }
      }
  }
}

// Main function
int main() {
  // Read the number n of vertices and m of edges
  std::cin >> n >> m;
  // Initialize the original adjacency matrix g; set all edge weights to infinity (0x3f usually represents a very large value)
  memset(g, 0x3f, sizeof(g));
  // Set the distance from each vertex to itself to 0
  for (int i = 1; i <= n; ++i) g[i][i] = 0;
  // Read m edges and build the original adjacency matrix g
  // For an undirected graph, edges are bidirectional; take the smaller weight
  for (int i = 0, u, v, w; i < m; ++i) {
    std::cin >> u >> v >> w;
    g[u][v] = g[v][u] = std::min(g[u][v], w);
  }
  // Copy the original adjacency matrix g to the shortest-path matrix dis
  memcpy(dis, g, sizeof(g));
  // Call Floyd to find a minimum cycle
  Floyd();
  // Determine whether a cycle exists from the minimum-cycle length
  if (ans == 1e9) {  // If the minimum-cycle length is still infinity, no cycle exists
    puts("No solution.");
  } else {
    // If a cycle exists, print its path vertices
    // std::cout << "ans = " << ans << std::endl; // Print the minimum-cycle length (commented out)
    // Print the path vertices, separated by spaces
    for (int i = 1; i <= cnt; ++i)
      std::cout << path[i]
                << (i == cnt ? "" : " ");  // There is no space after the last vertex
    std::cout << std::endl;                // Print a newline after the path
  }
  return 0;
}

Python

import copy
import sys

# Define a sufficiently large value to represent infinity
INF = sys.maxsize

def get_path(i, j, pos, path, cnt):
    """
    Recursively collect the intermediate vertices on a shortest path from vertex i to vertex j.

    Args:
        i (int): start vertex (0-based index).
        j (int): end vertex (0-based index).
        pos (list[list[int]]): matrix recording shortest-path intermediate vertices. pos[i][j] = k means that the shortest path from i to j passes through k.
        path (list[int]): list storing path vertices (using 0-based indices).
        cnt (int): current number of vertices in the path.

    Returns:
        int: updated number of vertices in the path.
    """
    # If pos[i][j] is -1, there is no intermediate vertex from i to j
    if pos[i][j] == -1:
        return cnt

    # Get the intermediate vertex k
    k = pos[i][j]
    # Recursively obtain the path from i to k
    cnt = get_path(i, k, pos, path, cnt)
    # Add the intermediate vertex k to the path
    path[cnt] = k
    cnt += 1
    # Recursively obtain the path from k to j
    cnt = get_path(k, j, pos, path, cnt)
    return cnt

def find_minimum_cycle_undirected(n, edges):
    """
    Find a minimum cycle in an undirected graph using the Floyd-Warshall algorithm.

    Args:
        n (int): number of graph vertices (1 through n).
        edges (list[tuple]): list of edges; each element (u, v, w) represents an edge of weight w between vertices u and v.
                             Vertex indices range from 1 to n.

    Returns:
        tuple: the minimum-cycle length and its path.
               Return (INF, []) if no cycle exists.
               The path is a list of vertex indices (1-based).
    """
    # Use 0-based indexing internally
    N = n
    # Initialize adjacency matrix g with the original edge weights
    g = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize shortest-path matrix dis, initially equal to g
    dis = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize matrix pos to record intermediate vertices on shortest paths
    pos = [[-1 for _ in range(N)] for _ in range(N)]

    # Initialize the diagonal to 0 (the distance from a vertex to itself)
    for i in range(N):
        g[i][i] = 0
        dis[i][i] = 0

    # Build the adjacency matrix from the input edges (undirected graph)
    for u, v, w in edges:
        # Convert 1-based indices to 0-based
        u -= 1
        v -= 1
        # For an undirected graph, edges are bidirectional
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
        dis[u][v] = min(dis[u][v], w)
        dis[v][u] = min(dis[v][u], w)

    # Initialize the minimum cycle length to infinity
    min_cycle_len = INF
    # Initialize the minimum-cycle path
    min_cycle_path = []

    # Core of the Floyd-Warshall algorithm
    # k is the intermediate vertex (0-based index)
    for k in range(N):
        # Before updating dis[i][j], check whether passing through k forms a shorter cycle
        # The cycle is i -> k -> j -> ... -> i
        # Here dis[i][j] is the shortest path considering vertices 0 through k-1 as intermediate vertices
        # The C++ code loops with i < k and j < i; we follow the same logic here (0-based)
        for i in range(k):  # 0 <= i < k
            for j in range(i):  # 0 <= j < i
                # Check whether i, k, and j form a cycle connected by dis[i][j]
                # Ensure that the original edges g[i][k] and g[k][j] exist (are not INF)
                # Also ensure that the shortest path dis[i][j] from i to j exists (is not INF)
                if g[i][k] != INF and g[k][j] != INF and dis[i][j] != INF:
                    current_cycle_len = g[i][k] + g[k][j] + dis[i][j]
                    if current_cycle_len < min_cycle_len:
                        min_cycle_len = current_cycle_len
                        # Reconstruct the path
                        path = [0] * (N + 5)  # Temporarily store the path in an array large enough
                        cnt = 0
                        # Add vertices to the path in the order i, k, j
                        path[cnt] = i
                        cnt += 1
                        path[cnt] = k
                        cnt += 1
                        path[cnt] = j
                        cnt += 1
                        # Get the intermediate vertices on the shortest path from j to i (using the previously computed dis and pos)
                        cnt = get_path(j, i, pos, path, cnt)
                        # Extract the actual path vertices (remove unused entries)
                        # Convert 0-based indices to 1-based
                        min_cycle_path = [node + 1 for node in path[:cnt]]

        # Standard Floyd-Warshall shortest-path update
        for i in range(N):
            for j in range(N):
                if (
                    dis[i][k] != INF
                    and dis[k][j] != INF
                    and dis[i][j] > dis[i][k] + dis[k][j]
                ):
                    dis[i][j] = dis[i][k] + dis[k][j]
                    # Record that the shortest path from i to j passes through k
                    pos[i][j] = k

    return min_cycle_len, min_cycle_path

# --- Main program entry point ---
if __name__ == "__main__":
    # Read the number n of vertices and m of edges
    n, m = map(int, sys.stdin.readline().split())

    # Read edge information
    edges = []
    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        edges.append((u, v, w))

    # Find the minimum cycle
    min_len, path = find_minimum_cycle_undirected(n, edges)

    # Output the result
    if min_len == INF:
        print("No solution.")
    else:
        # Print path vertices (1-based index), separated by spaces
        print(" ".join(map(str, path)))

Example 2

GDOI2018 Day 2 Patrol

Given an undirected graph with $n$ vertices and nonnegative edge weights, perform $q$ operations of three types:

Delete a vertex and all edges incident to it.
Restore a deleted vertex and all edges incident to it.
Query the size of the minimum cycle containing vertex $x$ .

For $50\%$ of the test data, $n,q \le 100$ .

For every simple cycle containing a vertex $x$ , there are two edges incident to $x$ ; removing either one turns the simple cycle into a simple path.

Therefore, enumerate the edges incident to $x$ , remove one of them each time, and run Dijkstra.

Alternatively, run Floyd from scratch for each query to find the minimum cycle, in $O(qn^3)$ time.

For $100\%$ of the data, $n,q \le 400$ .

We still use the Floyd-based minimum-cycle algorithm.

If no vertex has been deleted, deleting the queried vertex breaks each simple cycle into a simple path.

However, use Floyd to solve the second step instead.

Thus, we need the distances between every pair of vertices without passing through the queried vertex $x$ .

How can this be done online?

Force the problem offline, using an offline method to avoid the deletion operations.

Sort the queries by time and build a segment tree over them.

The active interval of each vertex covers all query times except those at which that vertex is queried. If a vertex is queried $x$ times, its active times can be viewed as $x + 1$ intervals, which are inserted into the segment tree.

Afterward, traverse the entire segment tree. When entering a vertex in the tree, save a copy of a Floyd array, then add all vertices inserted into that interval; when leaving, restore the saved array.

The time complexity is $O(qn^2\log q)$ .

There is also a faster online method.

For a query about vertex $x$ , run a shortest-path algorithm from $x$ , construct the shortest-path tree, and determine which subtree of $x$ contains each vertex.

Then there must be a non-tree edge whose endpoints lie in different subtrees of the root, such that this non-tree edge $+$ the two paths from its endpoints to the root forms a minimum cycle.

Proof:

Clearly, a minimum cycle contains a non-tree edge whose two endpoints lie in different subtrees of the root.

Suppose this edge is $(u,v)$ . The path from $x$ to $u$ in the shortest-path tree is a shortest path among all paths from $x$ to $u$ , and likewise for $x$ to $v$ . Therefore, the cycle $x\to u\to v\to x$ cannot be longer than the minimum cycle.

We can therefore enumerate all non-tree edges and update the answer.

The complexity of each query is that of one single-source shortest-path computation, namely $O(n^2)$ .

The total time complexity is $O(qn^2)$ .

Minimum Cycle

Introduction

Method

Brute-force Solution

Dijkstra

Process

Property

Floyd

Process

Recording Paths

Property

Implementation

Template Problem

Example 2