[algorithm]floyd Warshall

less than 1 minute read

Floyd-Warshall

참고:https://blog.naver.com/ndb796/221234427842

최단경로 알고리즘

최단경로: 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

  • 플로이드-와샬(Floyd-Warshall):모든 정점에서 모든 정점으로의 최단경로를 구하는 알고리즘
//그래프 초기화
for(int i = 0; i < number; i++>{
  for(int j = 0; j < number; j++){
    d[i][j] = a[i][j];
  }
})
//i -> j로 가는데 직접가는것보다 k를 경유하면 비용이 더 낮은경우 업데이트해간다.
//경유하는 k를 고려해 업데이트해감
//k = 거쳐가는 노드(경유)
for(int k = 0; k < number; k++){
  //i = 출발노드
  for(int i = 0; i < number; i++{
    //j = 도착노드
    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];
      }
    }
  })
}

특징

  • 다익스트라가 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬은 ‘거쳐가는 정점’을 기준으로 알고리즘을 수행
  • 다이나믹 프로그래밍에 기초한 알고리즘이다.
  • 시간 복잡도는 각 경유노드 k에 대해 출발(i),도착(j)쌍에 대해 계싼되므로 O(N^3)이다.

Updated: