hkucuk

Ford-Fulkerson Algorithm: Finding Maximum Flow

March 10, 2024 • ☕️ 5 min read • 🏷 computer, software, algorithm, graph, network

Translated by author into: English


Ford-Fulkerson algorithm is a graph algorithm that has an important place in network theory and aims to determine the maximum flow in a network. It is used to find the largest flow reaching a destination from a source in flow networks. To find this maximum flow, the algorithm discovers ascending paths and increases the flow along these paths.

The starting point of the algorithm is the assumption that the maximum flow is zero. Initially, there is no flow in the network, and the algorithm tries to find the maximum flow by gradually increasing this flow. At each incremental step, there is an incremental path and the flow along this path is increased. This incremental path is a path from the source to the destination, along which the flow can be increased. The Ford-Fulkerson algorithm is often implemented with the extended Depth First Search (DFS) algorithm. This algorithm finds increasing paths by visiting each node in the network and is used to increase the flow. The complexity of the algorithm varies depending on the network structure and the size of the maximum flow. But usually the time complexity is expressed as a function of the number of edges in the network and the size of the maximum flow.

How does it work?

  1. Initially, the maximum flow is assumed to be zero.
  2. Increasing paths are tried to be found. The ascending path is a path from the source to the destination, along which the flow can be increased.
  3. Once an increasing path is found, the flow along this path is increased.
  4. Unless the flow can be increased, that is, if the increasing path cannot be found, the algorithm ends.

Working Steps

  1. Determining Initial State and Starting Point: The Ford-Fulkerson algorithm aims to find the maximum flow in a network. The first step in this process is to determine the initial state and starting point of the network. The origin is usually the origin of the network and where the flow begins.
  2. Finding Increasing Paths: One of the steps that constitute the main operation of the algorithm is the discovery of ascending paths. In this step, potential increasing paths from the starting point to the target point are searched. Typically, these incremental paths are found using graph traversal algorithms such as extended Depth First Search (DFS) or Breadth First Search (BFS).
  3. Identification and Analysis of Ascending Paths: Analysis is performed on the increasing paths found. The capacity of each incremental path is determined and the lowest one is selected among these capacities. This is used to determine the amount by which the flow will be increased.
  4. Increasing Flow: The flow is increased by the capacity of the weakest link. This means updating the flow along the designated ascending path. The flow is increased as it moves from the starting point to the target point.
  5. Refactoring and Re-evaluation: By increasing the flow, capacities in the network are updated and paths that are no longer usable are marked. In this step, as a result of updating the flow, the network may need to be reorganized and the flow re-evaluated.
  6. Repetition and Termination: The steps of finding increasing paths, increasing the flow, and updating the network are repeated. This process ends when the incremental path can no longer be found and the flow cannot be increased. The algorithm terminates when the maximum flow is found or the flow cannot be increased.

Algorithm Complexity

The complexity of the Ford-Fulkerson algorithm generally depends on the network structure and maximum flow size. In the worst case, the time complexity can be O(Ef). Here E represents the number of edges in the network and f represents the maximum flow.

Usage areas

  • Network flow management
  • Transport and logistics systems
  • Telecommunication networks
  • Data transmission and network optimization

Ford-Fulkerson Algorithm implementation in GoLang:

package main

import "fmt"

// FordFulkerson is the implementation of Ford-Fulkerson algorithm
func FordFulkerson(graph [][]int, source, sink int) int {
	maxFlow := 0
	parent := make([]int, len(graph))

	for {
		flow := bfs(graph, source, sink, parent)
		if flow == 0 {
			break
		}
		maxFlow += flow

		// Update the residual capacities of the edges and reverse edges along the path
		v := sink
		for v != source {
			u := parent[v]
			graph[u][v] -= flow
			graph[v][u] += flow
			v = u
		}
	}
	return maxFlow
}

// Breadth First Search to find augmenting path
func bfs(graph [][]int, source, sink int, parent []int) int {
	visited := make([]bool, len(graph))
	queue := []int{source}
	visited[source] = true
	parent[source] = -1

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for v, capacity := range graph[u] {
			if !visited[v] && capacity > 0 {
				queue = append(queue, v)
				parent[v] = u
				visited[v] = true
			}
		}
	}
	if visited[sink] {
		pathFlow := 1 << 32
		v := sink
		for v != source {
			u := parent[v]
			pathFlow = min(pathFlow, graph[u][v])
			v = u
		}
		return pathFlow
	}
	return 0
}

// Helper function to find minimum of two integers
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	graph := [][]int{
		{0, 16, 13, 0, 0, 0},
		{0, 0, 10, 12, 0, 0},
		{0, 4, 0, 0, 14, 0},
		{0, 0, 9, 0, 0, 20},
		{0, 0, 0, 7, 0, 4},
		{0, 0, 0, 0, 0, 0},
	}

	source, sink := 0, 5
	maxFlow := FordFulkerson(graph, source, sink)
	fmt.Println("Maximum Flow:", maxFlow)
}

When the program is run, the output will be as follows.

Maximum Flow: 23

The working version of the program can be accessed here.

Ford-Fulkerson algorithm is an effective algorithm widely used to find the maximum flow in a network. It has an important place in graph theory and can be applied in many different fields. Understanding and applying this algorithm can make significant contributions in various fields such as network optimization, transportation and logistics problems.

Resources