Minimum Weight Cycle

By Admin / April 17, 2025

Given an undirected, weighted graph with V vertices numbered from 0 to V-1 and E edges, represented by a 2d array edges[][], where edges[i] = [u, v, w] represents the edge between the nodes u and v having w edge weight.
Your task is to find the minimum weight cycle in this graph.

Examples:

Input: V = 5, edges[][] = [[0, 1, 2], [1, 2, 2], [1, 3, 1], [1, 4, 1], [0, 4, 3], [2, 3, 4]]

Output: 6
Explanation:

Minimum-weighted cycle is 0 → 1 → 4 → 0 with a total weight of 6(2 + 1 + 3)

Input: V = 5, edges[][] = [[0, 1, 3], [1, 2, 2], [0, 4, 1], [1, 4, 2], [1, 3, 1], [3, 4, 2], [2, 3, 3]]

Output: 5
Explanation: 

Minimum-weighted cycle is 1 → 3 → 4 → 1 with a total weight of 5(1 + 2 + 2)

Constraints:
1 ≤ V ≤ 100
1 ≤ E = edges.size() ≤ 10³
1 ≤ edges[i][j] ≤ 100

Approach 01:

#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
public:
    int dijkstra(int source, int destination, unordered_map<int, vector<pair<int, int>>>& adjacencyList, int vertexCount) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        vector<int> minDistance(vertexCount, INT_MAX);

        minHeap.push({0, source});

        while (!minHeap.empty()) {
            int currentDistance = minHeap.top().first;
            int currentNode = minHeap.top().second;
            minHeap.pop();

            for (auto& neighbor : adjacencyList[currentNode]) {
                int neighborNode = neighbor.first;
                int edgeWeight = neighbor.second;

                // Skip the edge we're currently checking to form the cycle
                if ((currentNode == source && neighborNode == destination) ||
                    (currentNode == destination && neighborNode == source)) {
                    continue;
                }

                if (currentDistance + edgeWeight < minDistance[neighborNode]) {
                    minDistance[neighborNode] = currentDistance + edgeWeight;
                    minHeap.push({minDistance[neighborNode], neighborNode});
                }
            }
        }
        return minDistance[destination];
    }

    int findMinCycle(int vertexCount, vector<vector<int>>& edges) {
        unordered_map<int, vector<pair<int, int>>> adjacencyList;

        for (const auto& edge : edges) {
            int nodeU = edge[0];
            int nodeV = edge[1];
            int weight = edge[2];
            adjacencyList[nodeU].emplace_back(nodeV, weight);
            adjacencyList[nodeV].emplace_back(nodeU, weight);
        }

        int shortestCycleLength = INT_MAX;

        for (const auto& edge : edges) {
            int cyclePath = dijkstra(edge[0], edge[1], adjacencyList, vertexCount);
            if (cyclePath != INT_MAX) {
                shortestCycleLength = min(shortestCycleLength, cyclePath + edge[2]);
            }
        }

        return shortestCycleLength;
    }
};

import heapq
from typing import List
from collections import defaultdict

class Solution:
    def dijkstra(self, source: int, destination: int, adjacencyList: dict, vertexCount: int) -> int:
        minHeap = [(0, source)]
        minDistance = [float('inf')] * vertexCount

        while minHeap:
            currentDistance, currentNode = heapq.heappop(minHeap)

            for neighborNode, edgeWeight in adjacencyList[currentNode]:
                # Skip the edge being checked
                if (currentNode == source and neighborNode == destination) or \
                   (currentNode == destination and neighborNode == source):
                    continue

                if currentDistance + edgeWeight < minDistance[neighborNode]:
                    minDistance[neighborNode] = currentDistance + edgeWeight
                    heapq.heappush(minHeap, (minDistance[neighborNode], neighborNode))

        return minDistance[destination]

    def findMinCycle(self, vertexCount: int, edges: List[List[int]]) -> int:
        adjacencyList = defaultdict(list)

        for nodeU, nodeV, weight in edges:
            adjacencyList[nodeU].append((nodeV, weight))
            adjacencyList[nodeV].append((nodeU, weight))

        shortestCycleLength = float('inf')

        for nodeU, nodeV, weight in edges:
            cyclePath = self.dijkstra(nodeU, nodeV, adjacencyList, vertexCount)
            if cyclePath != float('inf'):
                shortestCycleLength = min(shortestCycleLength, cyclePath + weight)

        return shortestCycleLength

Time Complexity:

Building the Adjacency List:
Takes \( O(e) \), where \( e \) is the number of edges.
Dijkstra’s Algorithm per Edge:
Dijkstra runs in \( O((v + e) \log v) \), and we run it once for each edge, so total becomes \( O(e (v + e) \log v) \).
Total Time Complexity:
\( O(e (v + e) \log v) \)

Space Complexity:

Adjacency List:
Stores all edges: \( O(e) \)
Distance Vector and Priority Queue:
Each run of Dijkstra uses \( O(v) \) space.
Total Space Complexity:
\( O(e + v) \)

Leave a Comment Cancel Reply