hellogaon

네트워크 유량(Network Flow)은 네트워크 플로우라고도 불리며 이를 설명하기 전,유량 그래프(Flow Graph)에 대해서 먼저 알아봅시다.유량 그래프란 각 간선에 용량이라는 추가 속성이 존재하는 방향 그래프로각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 합니다.이 그래프에서는 소스(Source)와 싱크(sink)가 존재하며소스는 유량이 시작되는 정점, 싱크는 유량이 도착하는 정점을 뜻합니다.유량 그래프에서는 아래와 같은 3가지의 속성을 만족합니다. 1. 용량 제한 속성 : 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.2. 유량의 대칭성 : u에서 에서 v로 유량이 들어올 경우 v입장에서는 u로 음수의 유량을 보내는 것과 같다.3. 유량의 보존 : 소스와 싱크를 제외하고 각 정점에 들..

플로이드 와샬(Floyd Warshall)은 간선에 비용이 있는 그래프에서모든 점에서 모든 점까지의 최단거리를 구할 수 있는 모든 쌍 최단거리 알고리즘입니다.이 알고리즘은 반복적 동적 계획법과 슬라이딩 윈도우 기법을 사용하며dist[i][j]는 i 정점에서 j 정점까지의 최단거리를 뜻할 때거치는 점(k) - 출발점(i) - 도착점(j) 순의 3중 포문을 이용하여매 k마다 모든 i, j값을 순회하여 k 정점을 추가적으로 경유하였을 때의 값이 더 작은 경우(dist[i][j] > dist[i][k] + dist[k][j])dist[i][j]값을 갱신하여 최단거리를 저장합니다.3중 포문의 형태를 띄고 있으므로 시간복잡도는 정점 개수가 V일 때 O(V^3)이 되며코드가 매우 간결하므로 V가 크지 않을 경우의 최..

벨만 포드(Bellman Ford)는 간선에 비용이 있는 그래프에서시작점부터 다른 정점까지의 최단거리를 구할 수 있는 단일 시작점 최단거리 알고리즘입니다.이는 다익스트라 알고리즘과 동일하지만 간선의 비용이 음수일 때도 사용할 수 있습니다.벨만 포드 알고리즘은 다익스트라와 동일하게 dist배열을 사용하며 dist[i]는 시작점에서 i번 정점까지의 최단거리를 뜻합니다.시작점의 dist값은 0, 나머지 모든 정점은 무한대로 초기화 한 뒤 dist배열을 갱신하는 작업을 진행하는데최단 거리는 정점 개수가 V일 때 최대 V-1개의 간선을 거쳐야 한다는 원리를 이용하여V-1번의 루프를 돌며 k번째 루프에서는 시작점으로부터 k개의 간선을 거쳐 도달할 수 있는 최단 경로를 dist에 저장합니다.이 때 최단 거리가 V개 ..