# Dijkstra
1. Prim Algorithm과 유사하다.
https://thesulks.tistory.com/31
Prim ~ Dijkstra (BOJ1197 최소 스패닝 트리, BOJ1753 최단경로)
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를..
thesulks.tistory.com
# Bellman-Ford
1. 음수 사이클 (negative cycles)
음수 사이클은 |V|-1번 edge relaxation을 수행한 뒤 한 번 더 edge relaxation을 수행하여 확인할 수 있다.
이때 어떤 노드의 최단 거리가 한 번 더 갱신된다면 해당 그래프가 음수 사이클을 포함하고 있는 것이다.
# Floyd-Warshall
1. 음수 사이클 (negative cycles)
음수 사이클은 2차원 행렬 dist의 대각 성분을 비교하여 확인할 수 있다.
만약 대각 성분이 0이 아닌 음의 값을 갖는다면 해당 그래프가 음수 사이클을 포함하고 있는 것이다.
플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.[1][2] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R
ko.wikipedia.org
'Programming > Note' 카테고리의 다른 글
| Side effect & Pure function (0) | 2020.02.26 |
|---|---|
| 동적 계획법(Dynamic Programming)의 두 가지 속성 (0) | 2020.02.12 |
| Prim ~ Dijkstra (BOJ1197 최소 스패닝 트리, BOJ1753 최단경로) (0) | 2020.02.03 |
| Breadth First Search time complexity analysis (0) | 2020.01.21 |
| When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? (0) | 2020.01.21 |