Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜)

 

 

Algorithm 공부 #17 - 그래프(벨만-포드 / 플로이드 워셜)

 

 

벨만-포드 알고리즘(Bellman-ford-moore Algorithm)

 

  ● 그래프에서 최단거리를 구하는 알고리즘

  ● 음수 가중치 에지가 있어도 수행가능

  ● 시간 복잡도 O(VE), 음수 사이클 여부 판단 가능

  ● 벨만-포드 구현 방법

      1. 에지 중심으로 동작하므로 그래프를 에지 리스트로 표현(tuple로 출발지점, 도착지점, 가중치 삽입)

      2. 최단 거리 배열을 초기화(출발 지점은 0으로, 나머지는 무수히 큰 값으로 초기화)

      3. 최단 거리 배열에서 값이 가장 작은 노드를 고르기(일반적으로 출발 노드), N-1번 에지 사용 횟수를 반복하기

      4. 선택된 노드에 연결된 에지의 값을 바탕으로 다음 노드의 값을 업데이트

           최단거리 업데이트 : D[s]!=무한 && D[e] > D[s] + value로 최단 거리배열의 값 업데이트

      5. 음수 사이클 유무 확인하기 -> 모든 에지를 한 번씩 다시 사용하여 최단 거리배열의 값이 

          변하는지 확인하기/ 업데이트가 된다면 음수 사이클이 있으며, 위에서 도출한 최단 거리배열이 의미가 없음

 

 

 

백준 11657번 타임머신

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

※ 벨만포드 알고리즘 구현 문제 ※

● 에지 리스트 edges, 최단 거리 배열 mdistance생성 

● 에지리스트 입력 후 mdistance는 LONG_MAX로 초기화

● mdistance[시작지점] =0으로 만들고 N-1만큼 for문 돌리기

● 에지개수만큼 반복문을 돌리면서 최단거리 업데이트(mdistances[start]!=LONG_MAX여야함)

   mdistance[end] = min(mdistance[end], mdistance[start]+value)

● 최단거리를 다 업데이트 한 후에는 모든 에지개수만큼 반복문을 돌려서 최단거리배열의 변화 유무 체크

● 변화가 있으면 음수사이클이 있는 것이고 변화가 없으면 음수사이클이 존재하지 않음

 

#include<iostream>
#include<tuple>
#include<vector>
#include<limits.h>
using namespace std;

typedef tuple<int, int, int>edge;
vector<edge>edges;
vector<long>mdistances;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	mdistances.resize(N + 1);// 최단 거리 배열 크기 조절
	fill(mdistances.begin(), mdistances.end(), LONG_MAX); // 최단 거리 배열 초기화

	for (int i = 0; i < M; i++) { // 에지 리스트 업데이트
		int start, end,value;
		cin >> start >> end >> value;
		edges.push_back(make_tuple(start, end, value));
	}

	mdistances[1] = 0;
	for (int i = 1; i < N; i++) { // 벨만 포드는 N-1번씩 돌리므로
		for (int j = 0; j < M; j++) { // edge개수 만큼
			edge medge = edges[j];
			int start = get<0>(medge); // 출발점
			int end = get<1>(medge); // 도착 지점
			int value = get<2>(medge); // 가중치
			if (mdistances[start] != LONG_MAX && mdistances[end] > mdistances[start] + value) // 최단거리 업데이트
				mdistances[end] = mdistances[start] + value;		
		}
	}

	bool mycycle = false;
	for (int i = 0; i < M; i++) { // 모든 에지를 사용해 음수 사이클 여부 체크
		edge medge = edges[i];
		int start = get<0>(medge); // 출발점
		int end = get<1>(medge); // 도착 지점
		int value = get<2>(medge); // 가중치
		if (mdistances[start] != LONG_MAX && mdistances[end] > mdistances[start] + value) // 최단거리 업데이트
			mycycle = true; // 값이 더 줄어들면 음수사이클이 있다는 의미임
	}

	if (!mycycle) { // 음수 사이클이 없을 때
		for (int i = 2; i <= N; i++) {
			if (mdistances[i] == LONG_MAX)
				cout << -1 << '\n';
			else
				cout << mdistances[i] << '\n';
		}
	}
	else
		cout << -1 << '\n';
}

 

 

 

 

백준 1219번 오민식의 고민

https://www.acmicpc.net/problem/1219

1219번: 오민식의 고민

 

※ 벨만포드 알고리즘 응용 문제 ※

● 최단거리로 업데이트 하는 것이 아닌 최대 액수로 업데이트를 해주어야 함

● 반복문을 N+50번 정도로 크게 돌려서 양수 사이클의 여부를 확인하기

● 여러 가지 경우의 수 나누기

    1. mdistance[start] == LONG_MIN일 때 : 의미가 없으므로 continue;

    2. mdistnace[start]==LONG_MAX : 차피 탐색해야봐야 결과값은 LONG_MAX이므로 mdistance[end] = LONG_MAX

    3. 위의 두가지가 아니고 mdistance[end] < mdistance[start] +citymoney[end] - cost일 때

        최대 액수가 변경되므로 mdistance[end] = mdistance[start] + citymoney[end] - cost;

        만약 i>=N-1이고 3번 조건에 의해 변형되었으면 양수 사이클이 존재하는 것이므로 mdistance[end] =LONG_MAX;

        탐색 후 모든 에지를 돌려서 값이 변형되면 음수 사이클이 존재하는 것과 같은 의미

#include<iostream>
#include<tuple>
#include<vector>
#include<limits.h>
using namespace std;

typedef tuple<int, int, int>edge;
vector<edge>edges;
vector<long>mdistance;
vector<long>citymoney;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, startcity, endcity, M; // 입력 받기
	cin >> N >> startcity >> endcity >> M;

	mdistance.resize(N); // 거리 배열 초기화
	citymoney.resize(N); // 도시 머니 배열 초기화
	fill(mdistance.begin(), mdistance.end(), LONG_MIN); // 거리 배열 최솟값으로 초기화

	for (int i = 0; i < M; i++) { // 에지 리스트 업데이트
		int start, end, cost;
		cin >> start >> end >> cost;
		edges.push_back(make_tuple(start, end, cost));
	}
	for (int i = 0; i < N; i++) // 도시 머니 업데이트
		cin >> citymoney[i];
	mdistance[startcity] = citymoney[startcity];

	for (int i = 0; i <= N + 50; i++) { // 변형된 벨만 포드 알고리즘
		for (int j = 0; j < M; j++) {
			edge medge = edges[j];
			int start = get<0>(medge);
			int end = get<1>(medge);
			int cost = get<2>(medge);

			if (mdistance[start] == LONG_MIN) // 미방문 노드이므로 continue
				continue;
			else if (mdistance[start] == LONG_MAX) // 차피 최댓값이므로
				mdistance[end] = LONG_MAX;
			else if (mdistance[end] < mdistance[start] + citymoney[end] - cost) {
				mdistance[end] = mdistance[start] + citymoney[end] - cost; // 최댓값으로 업데이트
				if (i >= N - 1) // i가 여기부터는 양수 사이클 유무 판단
					mdistance[end] = LONG_MAX; // 양수 사이클이 존재하므로 최댓값을 바꿔줌(언젠가는 MAX를 찍음)
			}
		}
	}
	// 결괏값 출력
	if (mdistance[endcity] == LONG_MIN)
		cout << "gg";
	else if (mdistance[endcity] == LONG_MAX)
		cout << "Gee";
	else
		cout << mdistance[endcity];
}

 

 

 

 

플로이드-워셜 (Floyd-warshall Algorithm)

 

  ● 그래프에서 최단거리를 구하는 알고리즘

  ● 음수 가중치 에지가 있어도 수행가능

  ● 시간 복잡도 O(V^3)으로 느린 편 -> 주로 노드의 개수가 적게 제공

  ● 전체 경로의 최단거리는 부분 경로의 최단 거리의 조합으로 이루어진다는 점을 이용

  ● 플로이드-워셜 구현 방법

      1. 인접 행렬로 그래프를 구현 / S==E인 칸은 0으로 나머지는 모두 무한대로 초기화

      2. 인접 행렬에 각 출발점과 도착점의 가중치를 입력 

      3. 삼중 for문 구성 : 경유지 k에 관해(1~N/) / 출발 노드 S에 관해(1~N) / 도착 노드 E에 관해(1~N)

      4. 각 노드간의 최단거리르 업데이트함

           최단거리 업데이트 : D[S][E] = min(D[S][E] , D[S][K] + D[K][E]

   

 

 

백준 11404번 플로이드

https://www.acmicpc.net/problem/11404

11404번: 플로이드

   ※ 플로이드 워셜 알고리즘 구현 문제 ※

 

#include <iostream>
#include <vector>
#include <limits.h>
#include <tuple>
using namespace std;
static int N, M;
static long mdistance[101][101];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    for (int i = 1; i <= N; i++) { // 인접 행렬 초기화
        for (int j = 1; j <= N; j++) {
            if (i == j)
                mdistance[i][j] = 0;
            else
                mdistance[i][j] = 10000001; // 충분히 큰수로 저장
        }
    }

    for (int i = 0; i < M; i++) {
        int s, e, v;
        cin >> s >> e >> v;
        if (mdistance[s][e] > v) mdistance[s][e] = v;
    }
    for (int k = 1; k <= N; k++) { // 플로이드 워셜 알고리즘 수행
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (mdistance[i][j] > mdistance[i][k] + mdistance[k][j])
                    mdistance[i][j] = mdistance[i][k] + mdistance[k][j];
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mdistance[i][j] == 10000001) cout << "0 ";
            else cout << mdistance[i][j] << " ";
        }
        cout << "\n";
    }
}

 

 

 

백준 11404번 경로 찾기

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

   ※ 최단 거리를 구하는 과정에서 D[S][K]==1&&D[K][E]==1이면 경로가 있는 것이므로 D[S][E]=1 ※

#include<iostream>
#include<limits.h>
using namespace std;
long mdistance[101][101];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) { // 배열 초기화
		for (int j = 0; j < N; j++) {
			cin >> mdistance[i][j];
		}
	}

	for (int k = 0; k < N; k++) { // 경유지
		for (int i = 0; i < N; i++) { // 출발지
			for (int j = 0; j < N; j++) { // 도착지
				if (mdistance[i][k] == 1 && mdistance[k][j] == 1) // 최단 거리 업데이트
					mdistance[i][j] = 1;
			}
		}
	}

	for (int i = 0; i < N; i++) { // 결과 출력
		for (int j = 0; j < N; j++) {
			cout << mdistance[i][j] << " ";
			
		}
		cout << '\n';
	}
}

 

 

 

백준 1389번 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

   ※ 최단 거리를 구하는 과정에서 D[S][K]>=1&&D[K][E]>=1이면 친구 관계가 있는 것이므로

      D[S][E]=min(D[S][E], D[S][K]+D[K][E]); ※

 

#include<iostream>
#include<vector>
using namespace std;

int mdistance[101][101];
int main() {

	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) { // 배열 초기화
		for (int j = 1; j <= N; j++) {
			if (i == j)
				mdistance[i][j] = 0;
			else
				mdistance[i][j] = 100000;
		}
	}

	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		mdistance[start][end] = 1;
		mdistance[end][start] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (mdistance[i][k] >= 1 && mdistance[k][j] >= 1) {
					mdistance[i][j] = min(mdistance[i][j], mdistance[i][k] + mdistance[k][j]);
				}
			}
		}
	}
	int sum = 100001;
	int index = 0;
	for (int i = 1; i <= N; i++) {
		int s = 0;
		for (int j = 1; j <= N; j++) {
			s += mdistance[i][j]; //각 row더해주기
		}
		if (s < sum) {
			sum = s;
			index = i;
		}
	}
	cout << index;
}