벨만포드, SPFA

시작점을 정해줬을 때, 최단경로 알고리즘. 가중치가 음수여도 가능하다

 

*모든 간선을 돌면서 그에 속하는 정점에 대한 dist를 초기화할 수 있다면 초기화 해주는 작업을 정점개수-1만큼 반복한다.

O(EV)

 

필요한 것: 

 int dist[MAX]{0}

 vector<P> adj[MAX]; //혹은 vector<Edge> edge

 

<코드1>

일반적인 코드. 음의 사이클 검출방법

int main() {
	int N, M, dist[MAX], st, en;
	fill(dist, dist + N, INF);
	vector<P> adj[MAX];

	dist[st] = 0;
	bool minusCycle = false;
	for (int k = 0; k < N; k++) { // (N-1)번의 루프, N번째루프에 갱신되면 음의사이클존재
		//이하 두개의 for문 : 모든 간선에 대해..
		for (int from = 1; from <= N; from++) {
        	if(dist[from]==INF) continue; //시점으로부터 아직 도달 못함
			for (auto& p : adj[from]) {
				int next = p.first, d = p.second;
				if (dist[next] > dist[from] + d) {
					dist[next] = dist[from] + d;
					//N번째에 거리 갱신이 되는 경우 -> 음의 사이클
					if (k == N - 1) minusCycle = true;
				}
			}
		}
	}
}

 

<코드2>

약간 개선된 코드. 한 라운드에 단 한개의 정점에 대해서도 dist를 갱신하지 못한다면, 더이상 루프를 돌 필요가 없다. (최단경로가 모두 갱신된 것)

int n, m; 
vector<E> edge;
ll d[MAX];
int main() {
	FAST;
	cin >> n >> m;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		edge.push_back({ {u,v},w });
	}
 
	fill(d, d + MAX, 1e18);
	d[1] = 0;
	bool flag;
	for (int k = 0; k < n - 1; k++) {
		flag = false;
		for (E e : edge) {
			int from = e.first.first, to = e.first.second;
         	 	  if(d[from]==1e18) continue; //시점으로부터 도달 못함
			int w = e.second;
			if (d[to] > d[from] + w) {
				d[to] = d[from] + w;
				flag = true;
			}
		}
		if (!flag) break; //갱신이 한번도 이뤄지지 않았다면 더 볼 필요가 없다
	}
	for (int i = 1; i <= n; i++)
		cout << d[i] << " \n"[i==n];
}

 

<코드3>

SPFA (shortest path faster algorithm) using queue : 최악인 경우 시간복잡도 같지만, 평균적으로 O(E) 수행

매 라운드마다 다른 정점을 갱신시킬 여지가 있는 정점은, 그 전의 라운드에서 다른 정점에 의해 갱신된 정점이다.

그러한 정점만 큐에 넣어서 처리함으로써 좀더 효율적으로 짤 수 있다.

int n, m; 
vector<P> adj[MAX];
ll d[MAX];
int main() {
	FAST;
	cin >> n >> m;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
	}

	fill(d, d + MAX, 1e18);
	d[1] = 0;
    
	queue<int> q;
	q.push(1);
	bool c[MAX]{ 0 };
	c[1] = true;
	while(!q.empty()){
		int from = q.front(); q.pop();
		c[from] = false;
		for (P p : adj[from]) {
			int to = p.first, w=p.second;
			if (d[to] > d[from] + w) {
				d[to] = d[from] + w;
				if (!c[to]) { //갱신이 이뤄진 정점만 다음에 확인하면 된다.
					q.push(to);
					c[to] = true; //같은 정점을 두 번 이상 큐에 넣지 않도록 조절
				}
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << d[i] << " \n"[i==n];

 

 

나중에 최소비용 최대유량때 다시 나온다고 한다.

CSES에선 우선순위 큐를 사용하기도 한다.

 

기본문제

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

11657번: 타임머신