ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Floyd-Warshall
    알고리즘 2020. 3. 17. 15:29

    그래프에서 정점끼리의 최단 경로를구하는 문제 중

    다익스트라에 이어 플로이드 워셜 알고리즘에 대해 알아보도록 하자.


    Floyd-Warshall Algorithm 플로이드 워셜 알고리즘

    • 개념 : 모든 정점끼리의 최단 거리를 구하는 알고리즘
    • (다익스트라가 한 정점에서 다른 정점들까지였다면, 플로이드는 모든 정점들을 다 구하는 방법이다.)
    • (각 정점을 시작점으로 다익스트라 알고리즘을 반복하여도 되지만, 플로이드는 단 한번의 시행으로 모든 쌍을 구할 수 있다.)
    • 속성 

    Optimal substructure - 최단 경로의 부분경로는 역시 최단 경로다.

      (특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념)

    • 작동 방식

    -      정점(1,2, … , k) 이 있다고 가정해보자.

    -      C(k,u,v) : 1번 정점부터 k번 정점까지만을 경유점으로 썼을 때

       u에서 v까지 가는 최단 경로의 길이 u -> v / u -> (1,….,k) -> v

    -      C(k,u,v) = min(C(k,u,k) + C(k,k,v) , C(k,u,v))

    -      (u,v)로 가는 최단 경로에는 

      1) k를 거쳐가는 최단 경로 

      2) k를 거치지 않는 최단 경로 

      두가지가 존재한다.

    -      위 점화식을 사용하여 코드 작성

    •     모든 정점에 대한 경로를 계산하므로, 거리를 저장할 자료 구조는 다익스트라와 달리 2차원 배열을 사용한다.

            Dist[u][v] : 정점u에서 정점v로 가는 최단 거리

    •     다익스트라와 달리 음수 가중치에서 사용이 가능하다.



         

         (ex) 100개까지의 정점이 존재한다고 할때, 모든 정점들 사이의 최단 거리를 구하는 프로그램을 만들어보자.

      

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int n; //정점의 개수
    int INF = 999999999;
    int adj[101][101]; //거리를 저장하는 배열, 처음 초기값은 INF로 설정
     
    void Floyd() {
        for (int i = 1; i <= n; i++) {
            adj[i][i] = 0//자기 자신의 거리는 0으로 초기화
        }
     
        //k = 거쳐가는 노드
        for (int k = 1; k <= n; k++) {
            //i = 출발 노드
            for (int i = 1; i <= n; i++) {
                //시간 단축의 방법 ? i->k 경로가 있는지 확인, 없으면 pass
                if(adj[i][k] == INF) continue;
                //j = 도착 노드
                for (int j = 1; j <= n; j++) {
                    adj[i][j] = min(adj[i][k] + adj[k][j], adj[i][j]);
                }
                
            }
        }
     
    }
    cs


    '알고리즘' 카테고리의 다른 글

    Segment Tree  (0) 2020.03.17
    Greedy Algorithm  (0) 2020.03.17
    Dijkstra  (0) 2020.03.17
    Binary Serach  (0) 2020.03.16
    DP  (0) 2020.03.16

    댓글

Designed by Tistory.