DP를 사용하는 알고리즘들 #2

Shortest Path Problem

-벨만 포드 알고리즘 구현

Algorithm outline (negative cycle 이 없다 가정 시)

 

1.알고리즘은 총 0 ~ n-1 의 stage (iteration) 으로 구성되며, i 번째 stage 가 끝날 때  마다 G 의 모든 vertex v 에 대해 dist (i, v) 가 dist (v) 에 저장된다 (invariant).

2.0 번째 stage 에서는 앞선 base case 에 맞게 dist 값을 정해 준다.

3.이후 i 번째 stage 마다 모든 edge (u, v) 에 대해 다음 작업을 반복한다.

à dist (v) > dist(u) + w (u, v) 인 경우 dist (v) 를 dist (u) + w (u, v) 로 update

 

시간 복잡도 O(mn)

 

 

-프로이드 마샬 알고리즘 구현

 

1.알고리즘은 총 0 ~ n 의 stage (iteration) 으로 구성되며, k 번째 stage 가 끝날 때      마다 G 의 모든 vertex i, j 에 대해 dist (i, j, k) 가 dist (i, j) 에 저장된다 (invariant).

2.0 번째 stage 에서는 앞선 base case 에 맞게 dist 값을 정해 준다.

3.이후 k 번째 stage 마다 모든 vertex i, j 에 대해 다음 작업을 반복한다.

 

Time complexity

각 stage 마다 모든 1 ≤ i, j ≤ n 에 대해서 dist (i, j) 를 업데이트 x (n+1) 개의 stage

à O(n2 x (n+1)) = O(n3)

(m = Ω (n) 인 경우, Bellman-Ford 알고리즘을 n 번 반복하는 것보다 더 빠르다)

 

#include<iostream>
#include<vector>
#include<malloc.h>
#include<queue>
using namespace std;

const int INF = 9999;	//무한 대신 9999 사용
const int MAX = 100;	//MAX = 100

int adj[MAX][MAX];	//그래프

int dist[MAX];		//가중치
int ppt[8][8] = {
    //s ,a  ,b  ,c  ,d  ,e  ,f  ,g
    {INF,10 ,INF,INF,INF,INF,INF,8  },  //s
    {INF,INF,INF,INF,INF,2  ,INF,INF},  //a
    {INF,1  ,INF,1  ,INF,INF,INF,INF},  //b
    {INF,INF,INF,INF,3  ,INF,INF,INF},  //c
    {INF,INF,INF,INF,INF,-1 ,INF,INF},  //d
    {INF,INF,-2 ,INF,INF,INF,INF,INF},  //e
    {INF,-4 ,INF,INF,INF,-1 ,INF,INF},  //f
    {INF,INF,INF,INF,INF,INF,1  ,INF}   //g
};
int ppt2[4][4] = {
    //1, 2, 3, 4
    {INF,3  ,INF,5  },  //1
    {2  ,INF,INF,4  },  //2
    {INF,1  ,INF,INF},  //3
    {INF,INF,2  ,INF}   //4
};
int bellman_Ford()
{
    system("cls");
    int vertex_num, edge_num, start_point;	//점 갯수, 엣지 갯수, 시작점
    int S_index, E_index, d_w; //시작 포인트, 엔트 포인트, 가중치
    int num = 0;
    cout << "가중치 직접 입력 = 1번, ppt 행렬로 계산(시작점은 1번째) = 2번 : ";
    cin >> num;
    if (num == 1) {
        cout << "그래프의 점 갯수, 엣지 갯수, 시작점을 순서대로 입력해주세요";
        cin >> vertex_num >> edge_num >> start_point;
        //초기화
        for (int i = 1; i <= vertex_num; i++)
            for (int j = 1; j <= vertex_num; j++)
                adj[i][j] = INF;

        for (int i = 1; i <= vertex_num; i++)
            dist[i] = INF;

        for (int j = 0; j < edge_num; j++) {
            cout << "가중치 입력란입니다. 그래프의 시작점, 끝점과 가중치를 순서대로 입력해주세요";
            cin >> S_index >> E_index >> d_w;
            adj[S_index][E_index] = d_w;
        }
    }
    else {
        vertex_num = 8;
        edge_num = 8;
        start_point = 1;
        for (int i = 1; i <= vertex_num; i++)
            dist[i] = INF;
        for (int i = 1; i <= 8; i++) {
            for (int j = 1; j <= 8; j++) {
                adj[i][j] = ppt[i-1][j-1];
            }
        }
    }
    adj[start_point][start_point] = 0;        //시작점을 기준점으로 하기위해 0을 할당 
    dist[start_point] = 0;        //dist배열은 가중치가 저장됨
    //bellman-Ford Algorithm
    //update를 넣어준 이유 -> 뒤에꺼가 수정되었으면 다시 경로를 update해줘야하기때문
    bool update = 1;
    while (update)
    {
        update = 0;
        //가장 짧은 거리를 계산해서 넣어줌
        for (int v = 1; v <= vertex_num; v++) {
            for (int w = 1; w <= vertex_num; w++) {
                if (v != w && adj[v][w] != INF) {
                    if (dist[w] > dist[v] + adj[v][w]) {
                        dist[w] = dist[v] + adj[v][w];
                        update = 1;//경로 수정시 변환
                    }
                }
            }
        }
    }
    for (int i = 1; i <= 8; i++) {
        for (int j = 1; j <= 8; j++) {
            if (adj[i][j] == INF)
                cout << "INF";
            else
                cout << adj[i][j];
            cout << " ";
        }
        cout << endl;
    }
    for (int i = 1; i <= vertex_num; i++) {
        cout << "dist(" << i << ") : ";
        cout << dist[i] <<endl;
    }
    return 0;
}
int floyd_Warshall() {
    system("cls");
    int vertex_num, edge_num, start_point;	//점 갯수, 엣지 갯수, 시작점
    int S_index, E_index, d_w; //시작 포인트, 엔트 포인트, 가중치
    int num = 0;
    cout << "가중치 직접 입력 = 1번, ppt 행렬로 계산 = 2번 : ";
    cin >> num;
    if (num == 1) {
        cout << "그래프의 점 갯수, 엣지 갯수을 순서대로 입력해주세요";
        cin >> vertex_num >> edge_num ;
        //초기화
        for (int i = 1; i <= vertex_num; i++)
            for (int j = 1; j <= vertex_num; j++) {
                adj[i][j] = INF;
                if (i == j)
                    adj[i][j] = 0;
            }

        for (int j = 0; j < edge_num; j++) {
            cout << "가중치 입력란입니다. 그래프의 시작점, 끝점과 가중치를 순서대로 입력해주세요";
            cin >> S_index >> E_index >> d_w;
            adj[S_index][E_index] = d_w;
        }
    }
    else {
        vertex_num = 4;
        edge_num = 4;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                adj[i][j] = ppt2[i - 1][j - 1];
                if (i == j)
                    adj[i][j] = 0;
            }
        }
    }
    //floyd_warshall algorithm
    for (int mid = 1; mid <= vertex_num; mid++) {
        for (int start = 1; start <= vertex_num; start++) {
            for (int end = 1; end <= vertex_num; end++) {
                if (adj[start][end] > adj[start][mid] + adj[mid][end]) {
                    // 더 가까운 경로가 있을 경우 최신화
                    adj[start][end] = adj[start][mid] + adj[mid][end];
                }
            }
        }
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (adj[i][j] == INF)
                cout << "INF";
            else
                cout << adj[i][j];
            cout << " ";
        }
        cout << endl;
    }
    return 0;

}
int main() {
    int num;
    cout << "bellman_Ford = 1번 , folyd_warshall = 2번 : ";
    cin >> num;
    if (num == 1)
        bellman_Ford();
    else
        floyd_Warshall();
}

벨만 포드 알고리즘

시작점을 정해주고 그 점에 대해서 최단 거리가 출력된다.

시작 점만 정해지면 플로이드랑 다른 점이 거의 없다.

시간복잡도는 O(VE)

 

 

프로이드 마샬 알고리즘

모든 점에 대해서 최단 거리가 출력된다.

루프를 계속 돌려서 모든 쌍에 대해서 갱신 루프 순서는 경유지, 시작점, 끝점 순으로 돌림

시간 복잡도 O(n^3)