[개념] 6.Floyd Warshall 플로이드 와샬 알고리즘

플로이드 와샬(Floyd Warshall) 알고리즘이란?

모든 정점에서 모든 정점으로의 최단경로 구하는 알고리즘

 

X에서 Y로 가는 최소비용 VS X에서 거쳐가는 노드 Z로 가는 비용 + 노드 Z에서 Y로 가는 비용

 

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int number=4;
    int INF = 987654321;
    int arr[4][4] = {
        {0,5,INF,8},
        {7,0,9,INF},
        {2,INF,0,4},
        {INF,INF,3,0}
    };
    void floydwarshall(){
        int temp[4][4];
        memcpy(temp,arr,sizeof(arr));
        //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(temp[i][k] + temp[k][j]<temp[i][j]){
                        temp[i][j] = temp[i][k] + temp[k][j];
                    }
                }
            }
        }
    //결과출력
        for(int i=0; i<number;i++){
            for(int j=0; j<number;j++){
                cout<<temp[i][j]<<" ";
            }
            cout<<"\n";
        }
 
    }
    int main(){
        floydwarshall();
    }

**나동빈님 강의 정리하면서 공부한 내용입니다.

https://youtu.be/9574GHxCbKc

 

 

|본 포스팅은 쿠팡 파트너스의 일환으로 소정의 수수료를 제공받을 수 있음을 알립니다 |