#그래프

페이지당5 10 20

Network Flow

Network Flow란 유량 그래프란 간선의 가중치가 정점에서 정점으로 보낼 수 있는 최대 유량을 의미하는 그래프입니다. 최대 유량이란 해당 간선을 통해 동시에 흘려보낼 수 있는 물의 최대치입니다. 이러한 유량 그래프에서…

두 그룹으로 구분된 정점과, 서로 다른 그룹의 정점을 연결하는 간선들로 이루어진 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 그룹 A에 속하는 정점 Ai와 그룹 B에 속하는 정점 Bj를 연결하는 간선 (Ai,…

플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다. 하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는…

벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고…

다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다. 만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을…