TIL:플로이드-와샬 알고리즘

플로이드-와샬 알고리즘

• 모든 꼭지점 사이의 최단 경로를 구하는 알고리즘
• 음수 가중치를 갖는 간선의 경우 사이클이 없다면 처리 가능
• 반복문
  • 첫번째 : 중간 경로가 되는 꼭지점
  • 두번째 : 시작 경로가 되는 꼭지점
  • 세번째 : 도착 경로가 되는 꼭지점
• 시간 복잡도 : O(n³)

  for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
    	for(int j = 0; j < n; j++){
        	if(d[i][j] > d[i][k] + d[k][j]){
            	d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
  }
  

  ---

  선행 조건

• 2차원 배열 d는 두 정점 간의 연결이 없다면 무한대로 초기화
• 무한대가 아니라면 두 정점은 연결되어 있음