Dinic algorithm | Maximum Flow Problem | Network Flow | Graphs | Data Structure
In this video, I have discussed Dinic's algorithm to solve Maximum Flow Problem. In Dinic’s algorithm, we use BFS to check if more flow is possible and to construct level graph.
I have explained the algorithm using an example and have implemented in C++ as well.
00:00 Introduction
00:08 Define Maximum Flow Problem
02:21 Terminologies (Residual Capacity, Residual Graph, Augmenting Level Path)
03:24 Dinic's Algorithm Pseudo Code
16:32 C++ implementation
Source Code: https://github.com/fit-coder/fitcoder...
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For in-depth Graph theory and implementation details, please refer to the below videos:
Graphs Introduction: • Introduction to Graphs Data Structure
Graph representation:
Adjacency Matrix: • Graph representation I - Adjacency Matrix ...
Adjacency List: • Graph representation II - Adjacency List E...
Incidence Matrix: • Graph representation III - Incidence Matri...
Traversal techniques:
BFS, Breadth First Search: • BFS Breadth First Search | Graph Traversal...
DFS, Depth First Search: • DFS Depth First Search | Graph Traversal |...
Shortest Path algorithms:
Dijkstra algorithm: • Dijkstra Algorithm | Single Source Shortes...
Bellman Ford algorithm: • Bellman Ford Algorithm | Single Source Sho...
Floyd Warshall algorithm: • Floyd Warshall Algorithm | All Pairs Short...
Minimum Spanning Tree:
Kruskal algorithm: • Kruskal Algorithm | Minimum Spanning Tree ...
Prim algorithm: • Prim Algorithm | Minimum Spanning Tree | G...
Topological sort (Kahn algorithm): • Topological Sort | Kahn vs DFS | Graphs | ...
Articulation points / Cut vertices:
Tarjan algorithm: • Articulation Points | Cut Vertices | Tarja...
Disjoint Set / Union Find: • Disjoint Set | Union Find | Cycle Detectio...
Maximum Flow Problem:
Ford Fulkerson algorithm: • Ford Fulkerson Algorithm | Maximum Flow Pr...
Dinic algorithm:
Graph coloring / Chromatic number: • Graph Coloring | Chromatic Number | BackTr...
Hamiltonian cycle: • Hamiltonian Cycle (Circuit) | Hamiltonian ...
Euler cycle (Fleury algorithm): • Euler Cycle (Circuit) | Euler Path | Circu...
#DataStructure,#Graphs,#FitCoder,#Algorithm,#competitiveprogramming