Detecting negative cycle - Bellman-Ford algorithm

Algorithms  #algorithms  #graphs  #cycle-detection 

A negative cycle can be detected in a graph using the Bellman-Ford algorithm, which Dijkstra’s algorithm cannot.

Algorithm

As a part of the Bellman-Ford algorithm, each edge is relaxed for |V| - 1 time and distance improvement is measured. Following the edge relaxation, the algorithm is run again |V| - 1 time to check for negative cycles.

|V| = no. of vertices

Steps

1. Create a distance table of size |V| and set the initial value of all indices to positive infinity
2. Using edge relaxation, visit all vertices and update distances in the distance table
3. Repeat this process |V| - 1 time
4. After this iteration, run the same algorithm again |V| - 1 time, but this time set the vertex distance to negative infinity whenever it improves.
5. Lastly, if no vertex in the distance table has a value of negative infinity, the graph has no negative cycles, otherwise it has negative cycles.

Example

• Example 1. No negative cycles

• Example 2. Graph with negative cycle

• The following script finds negative cycles in the graphs given above.

fun example1Graph(): List<List<WeightedEdge>> {
    return mutableListOf<List<WeightedEdge>>().apply {
        add(0, listOf(
                WeightedEdge(1, 8),
                WeightedEdge(2, 7),
        )
        )

        add(
                1, listOf(
                WeightedEdge(2, 6),
                WeightedEdge(3, 5),
                WeightedEdge(4, -4),
        )
        )

        add(
                2, listOf(
                WeightedEdge(4, 9),
                WeightedEdge(3, -3),
        )
        )

        add(
                3, listOf(
                WeightedEdge(1, -2),
        )
        )


        add(
                4, listOf(
                WeightedEdge(3, 7),
                WeightedEdge(0, 2),
        )
        )
    }
}

fun example2Graph(): List<List<WeightedEdge>> {
    return mutableListOf<List<WeightedEdge>>().apply {
        add(0, listOf(
                WeightedEdge(1, -5),
        )
        )

        add(
                1, listOf(
                WeightedEdge(2, 2),
        )
        )

        add(
                2, listOf(
                WeightedEdge(0, -6),
        )
        )

        add(
                3, listOf(
                WeightedEdge(2, 3),
        )
        )
    }
}

fun main() {
    bellmanFordNegativeEdgeFinding(example1Graph()).also {
        println("Example 1: has negative cycle $it")
    }
    bellmanFordNegativeEdgeFinding(example2Graph()).also {
        println("Example 2: has negative cycle $it")
    }
}

//sampleStart
data class WeightedEdge(val value: Int, val weight: Int)

fun bellmanFordNegativeEdgeFinding(
        vertexToAdjacentEdges: List<List<WeightedEdge>>
): Boolean {
    // click + to see full script
    val distanceTable = Array(vertexToAdjacentEdges.size) { Double.POSITIVE_INFINITY }
    distanceTable[0] = 0.0
    // runs |V| - 1 time
    repeat(vertexToAdjacentEdges.size.dec()) {
        vertexToAdjacentEdges.forEachIndexed { vertex, weightedEdges ->
            weightedEdges.forEach { edge ->
                // relax edge
                val newDistance = distanceTable[vertex] + edge.weight
                if (newDistance < distanceTable[edge.value]) {
                    distanceTable[edge.value] = newDistance
                }
            }
        }
    }

    var hasNegativeCycle = false
    repeat(vertexToAdjacentEdges.size.dec()) {
        vertexToAdjacentEdges.forEachIndexed { vertex, weightedEdges ->
            weightedEdges.forEach { edge ->
                val newDistance = distanceTable[vertex] + edge.weight
                if (newDistance < distanceTable[edge.value]) {
                    // edge relaxed 2nd time, set it to infinity
                    distanceTable[edge.value] = Double.NEGATIVE_INFINITY
                    hasNegativeCycle = true
                }
            }
        }
    }
    return hasNegativeCycle
}
//sampleEnd

Exercise

• Find vertices effected by negative cycle