GNN Maximum Flow Problem (From Shusen Wang)

本文主要是介绍GNN Maximum Flow Problem (From Shusen Wang)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Maximum Flow Problem

ShusenWang 图数据结构和算法课程笔记 Slides

• Maximum Flow Problem
  • Description
    

• Naive Algorithm
  • Residual = Capacity - Flow
  • Left: Original Graph
  • Right: Residual Graph
    

- Bottleneck capacity = 2

- Iteration 2:- Find an augmenting path: s -> v_1 -> v_3 -> t- Update residuals

  - Remove saturated edge
- Iteration 3:- Find an augmenting path: s -> v_1 -> v_4 -> t- Update residuals

  - Remove saturated edge
- Iteration 4:- Cannot find an augmenting path: end of procedure
- Summay- Inputs: a weighted directed graph, the source 𝑠, and the sink 𝑡.- Goal: Send as much water as possible from 𝑠 to 𝑡- Constraints:- Each edge has a weight (i.e., the capacity of the pipe).- The flow must not exceed capacity.- naïve algorithm- Build a residual graph; initialize the residuals to the capacity. - While augmenting path can be found: - a. Find an augmenting path (on the residual graph.) - b. Find the bottleneck capacity 𝑥 in the augmenting path. - c. Update the residuals. (residual ← residual − 𝑥.)- The naïve algorithm can fail- The naïve algorithm always finds the blocking flow.- However, the outcome may not be the maximum flow.

• Ford-Fulkerson Algorithm

  • Problem with the naïve algorithm
    

  • Procedure
    
    
    
    
    
    
    
    
    
    
    
    
    

  • Worst-Case Time Complexity
    

  • Summary

    • Ford-Fulkerson Algorithm
      • Build a residual graph; initialize the residuals to the capacities
      • While augmenting path can be found:
        • Find an augmenting path (on the residual graph.)
        • Find the bottleneck capacity 𝑥 on the augmenting path.
        • Update the residuals. (residual ← residual − 𝑥.)
        • Add a backward path. (Along the path, all edges have weights of 𝑥.)
    • Time complexity: 𝑂(𝑓⋅𝑚). (𝑓 is the max flow; 𝑚 is #edges.)
• Edmonds-Karp Algorithm
  • Procedure
    • Build a residual graph; initialize the residuals to the capacities.
    • While augmenting path can be found:
      • Find the shortest augmenting path (on the residual graph.)
      • Find the bottleneck capacity 𝑥 on the augmenting path.
      • Update the residuals. (residual ← residual − 𝑥.)
      • Add a backward path. (Along the path, all edges have weights of 𝑥.)
  • Note: Edmonds-Karp algorithm uses the shortest path from source to sink. (Apply weight 1 to all the edges of the residual graph.)
  • Time complexity: $O(m^2\cdot n)$ . (m is #edges; n is #vertices.)
• Dinic’s Algorithm

  • Time complexity: $O(m\cdot n^2)$ . (m is #edges; n is #vertices.)

  • Key Concept: Blocking Flow
    

  • Key Concept: Level Graph
    

- Procedure

  - On the level graph, no flow can be found!- End of Procedure

- Summary1. Initially, the residual graph is a copy of the original graph. 2. Repeat: 1. Construct the level graph of the residual graph. 2. Find a blocking flow on the level graph. 3. Update the residual graph (update the weights, remove saturated edges, and add backward edges.)
- Time complexity: $O(m \cdot n^2)$ . (m is #edges; n is #vertices.)

• Minimum Cut Problem
  • statement
    

  - Capacity (S, T) = sum of weights of the edges leaving S.- In the figure, three edges leave S.- Capacity (S,T) = 2 + 2 + 2 = 6

- Max-Flow Min-Cut Theorem- In a flow network, the maximum amount of flow from s to t is equal to the capacity of the minimum s-t cut.- In short, amount of max-flow = capacity of min-cut.

- Algorithm- Run any max-flow algorithm to obtain the final residual graph.- E.g., Edmonds–Karp        algorithm or Dinic’s algorithm.- Ignore the backward edges on the final residual graph- Find the minimum s-t cut (S,T) :- On the residual graph, find paths from source 𝑠 to all the other vertices.- S ← all the vertices that have finite distance. (Reachable from s.)- T ← all the remaining vertices. (Not reachable from s.)
- Example

这篇关于GNN Maximum Flow Problem (From Shusen Wang)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---