목록최단경로문제 (3)

인생자취

최단 경로 문제 (3) 플로이드-워셜 알고리즘을 중심으로

1. 들어가기 지난 글에서는 경로의 가중치가 음수로 부여된 경우에 사용되는 벨만-포드 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 사용하는 알고리즘이긴 하나, 모든 노드간 최단 거리를 탐색하는 알고리즘인 플로이드-워셜(Floyd-Warshall)에 대해 알아볼 것이다. 2. 플로이드-워셜(Floyd-Warshall) 플로이드-워셜 알고리즘으 모든 정점의 쌍 사이에 최단 경로를 구할 수 있다. 다만, 음의 가중치의 순환(음수 사이클)이 없다는 가정 하에서 구할 수 있다. 모든 쌍의 최단 경로는 최단 경로의 부분 경로이므로, 경로의 부분 경로가 모여 곧 최단경로가 되는 형태이다. 그러므로 최단 경로를 구하는 상향식 접근방법이라 볼 수 있다. 플로이드-워셜 알고리즘은 모든 정점의 쌍..
개발/Dev | 알고리즘 2023. 7. 17. 13:09
최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로

1. 들어가기 지난 글에서는 경로의 가중치가 음이 아닌 수로 부여된 경우에 사용되는 다익스트라 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 단일 출발지의 최단 경로 문제를 해결하는 벨만-포드(Bellman-Ford) 알고리즘에 대해 알아볼 것이다. 2. 벨만-포드(Bellman-Ford) 벨만-포드 알고리즘은 출발 점으로부터 도달 가능한 음의 가중치의 순환(음수 사이클)이 존재하는 경우에는 최단경로를 구할 수 없고, 그러한 순환이 없다면 최단 경로들과 그 경로들의 가중치를 계산할 수 있다. 벨만-포드 알고리즘은 매번 모든 간선을 확인하므로 다익스트라 알고리즘보다는 느리다. 시간 복잡도는 O(VE); E는 경로(간선) 수, V는 꼭짓점(노드)의 수 이다. 하지만 간선이 음수로 존..
개발/Dev | 알고리즘 2023. 7. 14. 01:53
최단 경로 문제 (1) 다익스트라 알고리즘을 중심으로

1. 들어가기어떤 A지점에서 다른 B지점으로 이동하는 경로는 다양할 수 있다. 이는 네트워크에서도 마찬가지로 적용되는 부분이다. 연결 경로가 다양하게 존재할 수 있다. 경로가 다양하게 존재할 수 있는 가운데, 주목해야할 것은 가장 짧은 경로의 경우다. 이를 최단 경로라고 부른다. 최단 경로 문제는 다양한 경로 중 적은 비용으로 빠르게 이동하는 경로를 찾는 문제다. 이번 글에서는 최단 경로의 개념 및 이와 관련된 다익스트라 알고리즘에 대해 알아보고, 예제 문제를 살펴볼 것이다. 2. 최단경로어떤 가중치가 부여된 방향 그래프가 있다고 하자. 가중치가 부여된 그래프의 비용은 가중치를 계산하여 최단거리를 결정할 수 있다. 이때 가중치를 비용이라고 한다면 경로의 합이 가장 적은 경우가 최단 거리가 된다. 그리고 ..
개발/Dev | 알고리즘 2023. 7. 13. 02:11
Prev 1 Next