(전공복습) 데이터과학 4. 시각화
차례
벨만-포드 알고리즘
개요
다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다.
즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다.
다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사이클이 존재하는 경우 탐지할 수 있기 때문에 더 범용적이다.
기본적인 아이디어는 다익스트라 알고리즘과 유사한데, 항상 모든 엣지의 거리를 갱신한다는 차이만 존재한다
알고리즘의 순서는 다음과 같다:
- 출발점에서 각 노드까지의 거리를 무한대로 초기화한다.
- 출발점에서 출발점까지의 거리는 0으로 초기화한다.
- 모든 노드에 대해 다음의 과정을 반복한다.
- 모든 간선에 대해 다음의 과정을 반복한다. 이때, 각 과정에서 간선의 순서는 같아야 한다.
- (출발점과 각 노드의 거리) = min((출발점과 선택한 노드의 거리) + (선택한 노드와 각 노드의 거리), (출발점과 각 노드의 거리))
- 모든 간선에 대해 다음의 과정을 반복한다. 이때, 각 과정에서 간선의 순서는 같아야 한다.
예시
위 그래프를 출발점을 A로 하여 초기화한 모습이다.
간선을 갱신하는 순서를 (A, B), (A, C), (A, D), (C, B), (D, C)라 하자.
이 순서는 임의적인 것으로, 매 단계에서 같은 순서를 따른다는 가정 하에 간선의 갱신 순서는 어떻든 상관이 없다.
간선 (A, B)를 갱신한 모습이다.
노드 A의 거리가 0, 간선의 가중치가 2이므로 \(0+2=0\)이 된 모습이다.
간선 (A, C)를 갱신한 모습이다.
노드 A의 거리는 마찬가지로 0, 간선의 가중치는 4이므로 \(0+4=4\)가 된 모습이다.
간선 (A, D)를 갱신한 모습이다.
간선 (C, B)를 갱신한 모습이다.
노드 C의 거리는 4, 간선의 가중치는 -3이므로 \(4-3=1\)이 된다. 이 값은 원래 B의 거리인 2보다 작기 때문에 새로운 거리는 1로 갱신된다.
간선 (D, C)를 갱신한 모습이다.
노드 D의 거리는 2, 간선의 가중치는 -1이므로 \(2-1=1\)이 된다. 이 값은 원래 C의 거리인 4보다 작기 때문에 새로운 거리는 1로 갱신된다.
이렇게 되면 각 간선을 한 번씩 갱신하게 된다. 이 과정을 노드의 개수 \(V-1\), 즉 3번 반복해야 한다.
두 번째 반복에서, 간선 (A, B), (A, C), (A, D)를 갱신하는 과정에서는 아무 갱신도 일어나지 않는다.
따라서 각 노드까지의 거리는 그대로이다.
간선 (C, B)를 갱신하면 거리가 갱신된다.
원래 B까지의 거리는 1인데 비해, 노드 C까지의 거리는 1, 간선의 가중치는 -3이므로 \(1-3=-2\)로 더 작아졌으므로 갱신이 일어난다.
이후 간선 (D, C)에서는 갱신이 일어나지 않는다.
마지막(세 번째) 반복에서, 모든 간선에 대해 갱신이 일어나지 않는다.
따라서, 각 거리 (0, -2, 1, 2)가 각 노드까지의 최종 거리가 된다.
또한, 네 번째 반복에서도 마찬가지로 갱신이 없을 것이므로 음수 사이클 역시 존재하지 않는다는 것을 알 수 있다.
구현
반복문이 노드의 개수 \(V-1\)에 대해 각 간선 \(E\)번 일어나므로 최종적인 시간복잡도는 \(O((V-1)E)=O(VE)\)가 된다.
INF = float('inf')
# 노드의 개수
v = 4
# 엣지들의 목록
edges = [(0, 1, 2), (0, 2, 4), (0, 3, 2), (2, 1, -3), (3, 2, -1)]
distance = [INF] * v
distance[0] = 0
for i in range(v):
# v-1번 진행, 마지막은 음수 사이클의 존재 여부를 판별
for src, dst, cost in edges:
if distance[src] != INF and distance[src] + cost < distance[dst]:
distance[dst] = distance[src] + cost
if i == v-1:
print('음수 간선이 있습니다!')
print(distance)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...