최단 경로
[알고리즘 소개]
가중치가 존재하는 그래프에서 모든 정점들에 대해 최단경로를 구하는 알고리즘
[알고리즘 특징]
- dp
- 음수 가중치 가능
- 음수 사이클 불가능
- 최단 사이클 검출 가능
[코딩 방법]
- 이차원 배열 weight를 생성하고 INF로 값을 채움
- i == j인 부분은 0으로 채움
- 가중치가 w고 u → v인 간선들에 대해 weight[u][v] = w 저장
- 양방향 간선인 경우 weight[v][u]를, u와 v가 같고 w가 다른 경우는 최솟값을 저장
- 거쳐가는 정점 k를 기준으로 weight[i][j] = min(weight[i][j], weight[i][k] + [weight[k][j]) 갱신
[시간 복잡도]
$O(V^3)$
[공부용 링크]
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 파스칼의 삼각형 (Pascal's Triangle) (0) | 2021.03.26 |
|---|---|
| [알고리즘] 분할 정복을 이용한 거듭제곱 (0) | 2021.03.25 |
| [알고리즘] 유클리드 호제법 (Euclidean Algorithm) (0) | 2021.03.25 |
| [알고리즘] 벨만-포드 (Bellman-Ford) (0) | 2021.03.21 |
| [알고리즘] 다익스트라 (Dijkstra) (0) | 2021.03.18 |