[그래프] 최단 경로: 플로이드 와샬

📌 시간 복잡도

O(V^3)
V → 정점 개수

📌 어디에 쓰이는 알고리즘인가?

1.
그래프에서 모든 정점 사이의 최단 경로의 거리를 구할 수 있다.
2.
최단 경로 뿐만 아니라 연결되지 않은 경로도 알 수 있다.
board[i][j]와 board[j][i]를 돌면서 모두 INF면 경로가 없다는 의미이다.
둘중에 하나라도 INF가 아니면 경로가 있다는 의미이다.
for → i → for → j
여기서 board[i][j] & board[j][i]가 모두 INF면 해당 i는 경로가 없다.
public void check() { for (int i = 0; i < n; i++) { boolean possible = true; for (int j = 0; j < n; j++) { if (i == j) continue; if (board[i][j] == INF && board[j][i] == INF) { possible = false; break; } } if (possible) answer++; } }
Java

📌 주의점

1.
INF → 큰 값으로 초기화 할 때, 적당한 값을 넣어야 한다.
Integer.MAX_VALUE 절대 쓰지마라!
최단경로를 계산하기 위해 서로 더하면서, 오버플로우로 음수가 발생할 수 있다.

📌 구현

1.
2차원 배열을 i와 j가 같지 않은 곳에 INF로 초기화한다.
public int[][] initBoard(int n) { int[][] board = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) { board[i][j] = INF; } } } return board; }
Java
2.
간선 정보를 갱신한다.
3.
3중 for문을 순회한다.
a.
board[i][j]보다 board[i][k] + board[k][j]의 값이 더작다면 해당 값으로 변경
public void floyd(int n, int board) { for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (board[i][j] > board[i][k] + board[k][j]) board[i][j] = board[i][k] + board[k][j]; } } } }
Java

📌 관련 문제

TOP