벨만포드 알고리즘 | 자료구조실습 13주차 과제

1. 벨만포드 알고리즘 정리

 

[1] 벨만포드 정의

 

0. 알고리즘에서...

1) greedy : 선택의 순간에 눈 앞에 놓인 최적의 방안만 쫓아감

2) 분할 정복 : relax 하게 값을 갱신하며 찾아나감

 

==> 벨만포드 알고리즘은 방법 2)에 해당

 

1. 벨만포드(Bellman-ford) 알고리즘

방법

1) 첫번째 정점을 0으로 하고 나머지 정점을 모두 무한대로 설정한다.

2) 인접한 노드로 탐색하며 값을 비교하고, 비교값이 낮다면 갱신한다.

3) 2)의 과정을 모든 노드마다 반복한다.

 

특징

1) 벨만포드는 다익스트라보다 덜 직관적이다.

2) 음의 가중치가 있어도 문제를 풀 수 있다. (다익스트라는 가중치가 0 or 양수일 때만 사용 가능)

 

주의

* negative cycle이 있으면 안 된다

(만약 있을 경우 non-deterministic으로 간주. 알고리즘으로 풀기 어려운 문제임. -> 강화학습, 딥러닝 등으로 해결해야 함)

 

negative cycle이 등장하게 되면 최단 거리를 구할 때 계속 루핑이 반복되는 문제가 생긴다.

 

 

case2가 negative cycle에 해당한다.

 

 

 

 

[2] Shortest Path를 구하는 방법 ( Generic vs Bellman-ford )

1. Generic한 풀이 방법

1) initialize

d[w] <- ∞ (일단 무한대로 둔다)

F[v] <- NIL (결과)

d[s] <- 0 (시작점)

 

2) select edge & relax

 

relax :

if (d[v] > d[u] + w(u, v))

    d[v] <- d[u] + w(u,v)

 

 

2. Bellman-ford 풀이 방법

1) initialize

(위와 동일)

 

2) relax

for i = 0 to |v| - 1

    for each edge

        relax(u, v)

 

모든 정점에 대해 relax 시킴

 

3) check negative cycle

-> if not cycle: 정답

 

 

3) Bellman-ford 알고리즘을 이용한 풀이 예시

ex)

 

4) 알고리즘 코드

https://9327144.tistory.com/entry/%EC%B5%9C%EB%8B%A8-%EA%B1%B0%EB%A6%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

최단 거리 알고리즘 - 벨만-포드(Bellman-Ford) 알고리즘

 

해당 블로그의 코드를 참고하였다.

 

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

void bellman_ford(vector<vector<pair<int, int>>> edge, int start)
{
	vector<int> distance(edge.size(), INT_MAX);

	distance[start] = 0;

	for (int n = 0; n < edge.size() - 1; n++)
	{
		for (int i = 0; i < edge.size(); i++)
		{
			for (int j = 0; j < edge[i].size(); j++)
			{
				// 정점 i 에서 v 까지의 가중치 cost
				int v = edge[i][j].first;
				int cost = edge[i][j].second;

				// distance[i]의 값이 무한대인 경우는 판단하지 않는다.
				// 더해준 값이 더 작으면 갱신한다.
				if (distance[i] != INT_MAX && distance[v] > distance[i] + cost)
				{
					distance[v] = distance[i] + cost;
				}
			}
		}
	}

	for (int i = 0; i < edge.size(); i++)
	{
		for (int j = 0; j < edge[i].size(); j++)
		{
			int v = edge[i][j].first;
			int cost = edge[i][j].second;

			// 거리 값이 변경되는 경우 음의 사이클이 발생한 것이다.
			if (distance[i] != INT_MAX && distance[v] > distance[i] + cost)
			{
				cout << "음의 사이클 발생\n";
				return;
			}
		}
	}

	for (int i = 0; i < distance.size(); i++)
	{
		cout << start << " 에서 " << i << " 까지의 최단 거리 : " << distance[i] << endl;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<pair<int, int>>> edge;
	edge.push_back({ { 2,5 },{1,3 } }); // 1과 연결된 정점(정점값에서 -1한 값) & 가중치 값들을 추가 (인접 리스트)
	edge.push_back({ { 3,6 } });
	edge.push_back({ {1,6} });
	edge.push_back({ {1,-2} });

	bellman_ford(edge, 0);

	return 0;
}

 

 

2. Leet code 문제 풀이 : 743번 네트워크 딜레이 시간

 

 

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

 

풀어봤는데 어디가 틀렸는지 .... 도통 모르겠어서 일단 코드를... 올리겠다... 뭐지 뭐가 문제지

 

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> distance(n, INT_MAX);

        distance[0] = 0;

        for (int _n = 0; _n < n - 1; _n++) { //n-1번 반복
		    for (int i = 0; i < times.size(); i++) {
			    
				int u = times[i][0];
				int v = times[i][1];
				int w = times[i][2];

				if (distance[u] != INT_MAX && distance[v] > distance[u] + w)
				{
				    distance[v] = distance[v] + w;
				}
			    
		    }
	    }

	    for (int i = 0; i < times.size(); i++)
	    {
		    
			int u = times[i][0];
			int v = times[i][1];
			int w = times[i][2];

			if (distance[u] != INT_MAX && distance[u] > distance[v] + w)
			{
			    return -1;
			}
	    }
    if(distance[k] == INT_MAX) return -1;
    return distance[k];

    }
};