최단 거리3 [Algorithm] 플로이드-워셜 알고리즘 (Floyd-Warshall) 모든 최단 경로를 구하는 알고리즘이다. 한 번 실행으로 모든 노드간의 최단 경로를 구할 수 있다. 음의 가중치가 있는 그래프에서도 최단 거리를 구할 수 있다. $ O(V^3) $의 시간 복잡도를 가진다. (V : 정점(vertex)의 개수) 알고리즘 1. 최단 거리 테이블을 초기화한다. 2. 임의의 노드 s와 e 사이의 노드 m을 설정한다. 3. 현재 노드 s에서 노드 e로 가는 거리와, 노드 m을 거쳐서 가는 거리를 비교하여 최단 거리 테이블을 업데이트한다. 4. 3번의 과정에 대해 s와 e의 가능한 모든 경우의 수 정점의 개수$ ^ 2 (V ^ 2) $만큼 반복해준다. 5. 2번의 과정에 대해 모든 가능한 경우 점점의 개수(V) 만큼 반복해준다. 주의할 점 벨만-포드 알고리즘과 마찬가지로 음의 가중치.. 2023. 6. 6. [Algorithm] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 음의 가중치가 있는 그래프에서도 최단 거리를 구할 수 있는 알고리즘이다. 모든 경우의 수를 탐색하는 알고리즘으로 $ O(VE) $의 시간복잡도를 가진다. (V : 정점(vertex)의 개수, E : 간선(Edge)의 개수) 알고리즘 1. 시작 정점과 도착 정점을 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 모든 간선을 탐색한다. 4. 간선의 시작 정점이 계산 된 적이 있는 정점이라면 그 간선의 거리를 계산해 테이블을 업데이트한다. 5. 3~4의 과정을 정점의 개수(V)만큼 반복 실행한다. 주의할 점 음의 가중치가 존재하므로 그래프에서 위의그림과 같은 돌면 돌 수록 거리가 짧아지는 음의 사이클이 존재할 수 있다. 음의 사이클이 존재하면 결국 음의 무한대로 발산하므로 정확한 최단거리를 구할 수 없다.. 2023. 6. 5. [Algorithm] 다익스트라 알고리즘 (Dijkstra's Algorithm) 음의 가중치가 없는 그래프에서 최단거리를 구하는 알고리즘이다. 음의 가중치를 가지는 간선이 존재하면 거리의 합이 음수 무한대로 발산하기 때문에 이 알고리즘은 사용할 수 없다. 에츠허르 다익스트라가 고안한 알고리즘은 $ O(V^2) $ 의 시간 복잡도를 가진다. (V : 정점(vertex)의 개수) 우선순위 큐(힙 트리)를 이용한 개선된 알고리즘에서는 $ O((V + E) logV) $의 시간복잡도를 가진다. (V : 정점(vertex)의 개수, E : 간선(edge)의 개수) 알고리즘 1. 시작 정점과 도착 정점을 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 현재 정점에서 인접한 정점 중 "미방문" 상태인 정점들을 찾고, 거리를 비교하여 최단 거리 테이블을 업데이트한다. 4. 현재 정점을 "방문.. 2023. 6. 5. 이전 1 다음