문제풀다가 모든 점에 대한 최단경로를 구해야하는 문제를 풀다가 플로이드 와샬을 떠올랐지만 알고리즘을 까먹엇다.
(대충 3중 for문 이라는 것 정도..)
특징
다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘.
플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘.
3중 for 문
- (제일 밖) 첫 번째
for
문: 거쳐가는 노드 - 두 번째
for
문 : 출발 노드 - 세 번째
for
문 : 도착 노드
검증
출발→거쳐
+거쳐→도착
가출발→도착
보다 더 짧으면?출발→도착
갱신.
Code
for(int k = 0; k < number ; k++) {
for(int i = 0; i < number ; i++) {
for(int j = 0; j < number ; j++) {
if (d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}
'👨🏻💻 Development > 𝐀 Algorithm' 카테고리의 다른 글
2021년 09월 10일 TIL - 이진 탐색 (0) | 2021.09.10 |
---|---|
2021년 09월 08일 TIL - Heap (Java) (0) | 2021.09.08 |
2021년 09월 06일 TIL - 2차원 배열 돌리기( N * M) (0) | 2021.09.06 |
2021년 09월 06일 TIL - 다익스트라 알고리즘 (Java) (0) | 2021.09.06 |
문제풀다가 모든 점에 대한 최단경로를 구해야하는 문제를 풀다가 플로이드 와샬을 떠올랐지만 알고리즘을 까먹엇다.
(대충 3중 for문 이라는 것 정도..)
특징
다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘.
플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘.
3중 for 문
- (제일 밖) 첫 번째
for
문: 거쳐가는 노드 - 두 번째
for
문 : 출발 노드 - 세 번째
for
문 : 도착 노드
검증
출발→거쳐
+거쳐→도착
가출발→도착
보다 더 짧으면?출발→도착
갱신.
Code
for(int k = 0; k < number ; k++) {
for(int i = 0; i < number ; i++) {
for(int j = 0; j < number ; j++) {
if (d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}
'👨🏻💻 Development > 𝐀 Algorithm' 카테고리의 다른 글
2021년 09월 10일 TIL - 이진 탐색 (0) | 2021.09.10 |
---|---|
2021년 09월 08일 TIL - Heap (Java) (0) | 2021.09.08 |
2021년 09월 06일 TIL - 2차원 배열 돌리기( N * M) (0) | 2021.09.06 |
2021년 09월 06일 TIL - 다익스트라 알고리즘 (Java) (0) | 2021.09.06 |