시작 정점에서 목적 정점으로 한 패스를 통해서 흘릴 수 있는 최대 용량을 구하는 문제.
그림에서는 3 ( 1 - 2 - 3 - 4)
이는 greedy method(dijkstra의 최단 거리와 유사)을 이용하여 source 에서 흘릴 수 있는 최대 용량을 구할 수 있음
초기화 : 소스1 을 용량을 무한대(아주크게)로 둠
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | x | 무한대 | 없음 |
| 2 | x | x | 없음 |
| 3 | x | x | 없음 |
| 4 | x | x | 없음 |
- 방문되지 않은 노드 중 최대용량을 선택 ... 1 번 정점 선택
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | x | x | 없음 |
| 3 | x | x | 없음 |
| 4 | x | x | 없음 |
-1 번 정점에서 갈 수 있는 정점에서 갈수 있는 길 갱신
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | x | 5 | 1 |
| 3 | x | 2 | 1 |
| 4 | x | 0 | 없음 |
-방문 되지 않은 정점 중 최대 정점 선택 ... 2 번 정점
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | o | 5 | 1 |
| 3 | x | 2 | 1 |
| 4 | x | 0 | 없음 |
- 2 번 정점에서 갈수 있는 용량과 방문되지 않은 정점의 용량과 비교후 update
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | o | 5 | 1 |
| 3 | x | 3 | 2 |
| 4 | x | 1 | 2 |
- 방문되지 않은 정점중 최대는 정점 3
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | o | 5 | 1 |
| 3 | o | 3 | 2 |
| 4 | x | 1 | 2 |
- 선택된 3 번 정점의 용량은 3 , 3 번 정점에서 5 번 정점으로의 용량은 5 하지만 5 만큼 흘릴수는 없으므로 3 으로 비교 후 update
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | o | 5 | 1 |
| 3 | o | 3 | 2 |
| 4 | x | 3 | 3 |
- 방문되지 않은 정점 중 최대는 4 ... 이는 sink... 용량은 3
| 정점 | 방문유무 | 최대 용량 | 아버지정점 |
| 1 | o | 무한대 | 없음 |
| 2 | o | 5 | 1 |
| 3 | o | 3 | 2 |
| 4 | o | 3 | 3 |