[알고리즘] 최단 경로 알고리즘 : 플로이드 와샬 (Floyd Warshall)

플로이드 와샬(Floyd Warshall)

• 모든 쌍의 최단 거리 알고리즘
• 두 정점 사이에 간선이 없는 경우 어떤 경로의 길이보다도 큰 값으로 처리
• 3중 for문 사용
• 자기 자신으로 가는 간선은 항상 0으로 초기화

int n; // 정점의 수
int m; // 간선의 수
int adj[][] = new int[n+1][n+1]; // 그래프의 인접행렬 

// 간선이 없는 경우 어떤 경로의 길이보다 큰 값으로 초기화
// 자기 자신으로 가는 간선 0으로 초기화
for(int i = 0; i < n+1; i++) {
	Arrays.fill(adj[i], 10000001);
	adj[i][i] = 0;
}

//  u -> v 로 향하는 가중치 w를 가지는 간선
for(int i = 0; i < m; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	int u = Integer.parseInt(st.nextToken());
	int v = Integer.parseInt(st.nextToken());
	int w = Integer.parseInt(st.nextToken());
	adj[u][v] = w;
    // 양방향 그래프일경우 추가
    // adj[v][u] = w;
}

// i -> j의 경로와 경유점 k를 거쳐 i -> k -> j로 가는 경로 중 최소 가중치를 가진 경로 선택
for(int k = 1; k < n+1; k++) {
	for(int i = 1; i < n+1; i++) {
		for(int j = 1; j < n+1; j++) {
			adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
		}
	}
}