Negative Cycle Detection

When detecting negative cycles reachable from a starting node, two primary algorithms are used: Bellman-Ford and SPFA (Shortest Path Faster Algorithm).

In the Bellman-Ford algorithm, shortest paths are computed over n-1 iterations. If a relaxation is still possible during the n-th iteration for any edge where the source node is reachable, a negative cycle exists. It is critical to ensure that the source node's distance is not infinite before attempting relaxation.

#include <iostream>
#include <vector>

const int MAX_VAL = 0x3f3f3f3f;

struct Connection {
    int src, dest, weight;
};

void findNegativeCycle() {
    int vertices, edges;
    std::cin >> vertices >> edges;
    std::vector<Connection> graph;
    std::vector<int> distance(vertices + 1, MAX_VAL);
    distance[1] = 0;

    for (int i = 0; i < edges; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        graph.push_back({u, v, w});
        if (w >= 0) {
            graph.push_back({v, u, w});
        }
    }

    bool updated;
    for (int i = 1; i < vertices; ++i) {
        updated = false;
        for (const auto& conn : graph) {
            if (distance[conn.src] != MAX_VAL && distance[conn.dest] > distance[conn.src] + conn.weight) {
                distance[conn.dest] = distance[conn.src] + conn.weight;
                updated = true;
            }
        }
        if (!updated) break;
    }

    for (const auto& conn : graph) {
        if (distance[conn.src] != MAX_VAL && distance[conn.dest] > distance[conn.src] + conn.weight) {
            std::cout << "YES\n";
            return;
        }
    }
    std::cout << "NO\n";
}

int main() {
    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        findNegativeCycle();
    }
    return 0;
}

SPFA optimizes Bellman-Ford using a queue. To detect a negative cycle, maintain a count of how many times each vertex enters the queue. If any vertex is enqueued n or more times, and its distance is finite, a negative cycle is present.

#include <iostream>
#include <vector>
#include <queue>

const int MAX_VAL = 0x3f3f3f3f;

struct Connection {
    int target, weight, next;
};

void findNegativeCycleSPFA() {
    int vertices, edges;
    std::cin >> vertices >> edges;
    
    std::vector<Connection> graph(edges * 2 + 1);
    std::vector<int> head(vertices + 1, -1);
    std::vector<int> distance(vertices + 1, MAX_VAL);
    std::vector<bool> in_queue(vertices + 1, false);
    std::vector<int> push_count(vertices + 1, 0);
    
    int current_edge = 0;
    for (int i = 0; i < edges; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        
        graph[++current_edge] = {v, w, head[u]};
        head[u] = current_edge;
        
        if (w >= 0) {
            graph[++current_edge] = {u, w, head[v]};
            head[v] = current_edge;
        }
    }
    
    std::queue<int> q;
    q.push(1);
    distance[1] = 0;
    in_queue[1] = true;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        in_queue[curr] = false;
        
        for (int i = head[curr]; i != -1; i = graph[i].next) {
            int next_node = graph[i].target;
            int new_dist = distance[curr] + graph[i].weight;
            
            if (distance[next_node] > new_dist) {
                distance[next_node] = new_dist;
                if (!in_queue[next_node]) {
                    q.push(next_node);
                    in_queue[next_node] = true;
                    push_count[next_node]++;
                    if (distance[next_node] < MAX_VAL / 2 && push_count[next_node] >= vertices) {
                        std::cout << "YES\n";
                        return;
                    }
                }
            }
        }
    }
    std::cout << "NO\n";
}

int main() {
    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        findNegativeCycleSPFA();
    }
    return 0;
}

Second Shortest Path

Finding the second shortest path between two nodes can be achieved by executing Dijkstra's algorithm twice: once from the start node to compute distances to all other nodes, and once from the destination node on the reversed graph to compute distances from all nodes to the destination. By iterating over all edges, a candidate alternative path can be evaluated by temporarily diverging through a single edge and rejoining the optimal route, ensuring the resulting distance is strictly greater than the shortest path.

All-Pairs Shortest Paths

When a problem requires calculating the total distance along a predetermined sequence of waypoints, the Floyd-Warshall algorithm efficiently precomputes the shortest distances between every pair of nodes. The final answer is obtained by summing the distances between consecutive waypoints in the provided sequence.

#include <iostream>

const long long INF = 1e18;

long long dist[105][105];
long long waypoints[10005];

void computeAllPairs(int n) {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; ++i) std::cin >> waypoints[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> dist[i][j];
        }
    }
    
    computeAllPairs(n);
    
    long long total_distance = 0;
    for (int i = 2; i <= m; ++i) {
        total_distance += dist[waypoints[i-1]][waypoints[i]];
    }
    std::cout << total_distance << "\n";
    return 0;
}

Transitive Closure

Transitive closure determines reachability between all pairs of vertices in a directed graph. Using a Floyd-Warshall-like approach, we can update the reachability matrix. If vertex i can reach k and k can reach j, then i can reach j. The logical operation uses bitwise AND and OR, as standard addition is invalid for boolean reachability states.

#include <iostream>

int reachability[105][105];

void computeTransitiveClosure(int n) {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                reachability[i][j] = reachability[i][j] | (reachability[i][k] & reachability[k][j]);
            }
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> reachability[i][j];
        }
    }
    
    computeTransitiveClosure(n);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j > 1) std::cout << " ";
            std::cout << reachability[i][j];
        }
        std::cout << "\n";
    }
    return 0;
}