-
2021.07.22
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든 쌍 최단 경로(All-Pairs Shortest Path)를 구하는 알고리즘 O(V³)의 시간 복잡도와 O(V²)의 메모리 사용량으로 동작하는 상향식 알고리즘 벨만-포드 알고리즘 그래프의 두 정점 사이의 최단 경로가 출발 정점에서 시작하는 다른 최단 경로와 최종 목표 정점으로 연결된 에지의 조합으로 구성됨. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 은 이러한 개념에 좀 더 광범위한 일반화를 적용함으로써 큰 효과를 얻음. 정점 A와 정점 B 사이의 최단 거리가 AB이고, 정점 B와 정점 C 사이의 최단 거리가 BC이면, 정점 A와 정점 C 사이의 최단 거리는 AB + BC 임. 이 논리는 그 자체로 획기..
-
2021.07.04
존슨 알고리즘(Johnson's Algorithm)
존슨 알고리즘(Johnson's Algorithm) 벨만-포드 알고리즘 과 다익스트라 알고리즘 의 방법을 결합하여 모든 정점 사이의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 효율성을 활용함과 동시에 음수 가중치를 갖는 그래프에 대해서도 올바른 결과를 생성할 수 있음. 상당히 새로운 접근 방법을 사용함. 음수 가중치에 대한 다익스트라 알고리즘의 한계를 극복하기 위해 전체 에지 가중치를 음수가 아닌 형태로 변환 함. 벨만-포드 알고리즘 과 적절한 수학 논리 를 결합하여 이루어짐. 동작 방식 그래프에 새로운 더미(Dummy) 정점 을 추가함. 그리고 이 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결함. 이후 벨만-포드 알고리즘 을 이용하여 더미 정점과 나머지 정점들 사이의 최단 경로..
-
2021.07.02
벨만-포드 알고리즘(Bellman-Ford Algorithm)
벨만-포드 알고리즘(Bellman-Ford Algorithm) 음수 가중치가 있는 그래프를 다룰 때 사용하는 알고리즘 그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾음. V : 정점의 개수 다익스트라 알고리즘보다 높은 점근적 시간 복잡도를 가짐. 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공함. 코드 1 음수 가중치 사이클 이 없을 경우 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edge..
