FordFulkersonalgoritmen

Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm is a method used to find the maximum flow in a flow network, which is a graph where each edge has a capacity. This algorithm was first described by L. R. Ford and D. R. Fulkerson in 1956. The algorithm works by finding the augmenting paths in the residual graph of the flow network, which is then used to improve the flow in the original graph.

The algorithm starts by initializing the flow in the network to zero. It then repeatedly finds an augmenting path in the residual graph, which is a path between the source and the sink in the graph with no edges with zero capacity. The capacity of the edges along the augmenting path is then used to calculate the maximum flow that can be sent along the path, and the excess flow is added to the network. This process is repeated until no more augmenting paths can be found in the residual graph.

The algorithm returns the maximum flow in the network, which is the maximum amount that can be sent from the source to the sink in the network. The Ford-Fulkerson algorithm has a high time complexity, but it is simple to implement and can be used for small to medium-sized networks. It has applications in computer networks, transportation networks, and financial networks, among others. The algorithm has been widely used and is considered a classic algorithm in the field of algorithms and network flows.