단일 시작점 최단 경로 알고리즘. 근데 음수 간선이 있을 때도 가능. 음수 간선 사이클이 있어서 최단 거리가 정의되지 않는 경우 이를 발견 가능.

시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여나가는 방식으로 동작.

수행 과정에서 각 정점까지의 최단 거리의 상한을 담은 배열 upper[ ]를 유지한다. 이 값은 알고리즘이 진행됨에 따라 점점 줄어들고, 알고리즘 종료할 때는 실제 최단 거리를 담는다.

동작 과정

• 시작점에서 시작점까지 거리 0 → upper[s] = 0으로 초기화
• 나머지 원소들은 INF로 초기화
• dist[v] ≤ dist[u] + w(u,v) 라는 조건이 항상 참이라는 것을 이용해서 upper의 값을 더 실제 최단 거리에 가깝게 보정. (만약 dist[v] = 50, dist[u] = 10, w(u,v) = 30이라면, 이는 모순이다. s→u + u→v가 40인데 dist[v] = 50?)

// 정점의 개수
int V;
// 그래프의 인접 리스트. (연결된 정점 번호, 간선 가중치) 쌍을 담는다.
vector<pair<int,int>> adj[MAX_V];
// 음수 사이클이 있을 경우 텅 빈 배열을 반환
vector<int> bellmanFord(int src)
{
	// 시작점을 제외한 모든 정점까지의 최단 거리 상한을 INF로 둔다.
	vector<int> upper(V, INF);
	upper[src] = 0;
	bool updated;
	// v번 순회한다.
	for (int iter = 0; iter < V; ++iter)
	{
		updated = false;
		for (int here = 0; here < V; ++here)
		{
			for (int i = 0; i < adj[here].size(); ++i)
			{
				int there = adj[here][i].first;
				int cost = adj[here][i].second;
				// (here, there) 간선을 따라 완화를 시도한다.
				if (upper[there] > upper[here] + cost)
				{
					// 성공
					upper[there] = upper[here] + cost;
					updated = true;
				}
			}
		}
		// 모든 간선에 대해 완화가 실패했을 경우 V-1번도 돌 필요 없이 곧장 종료
		if (!updated) break;
	}
	// V번째 순회에서도 완화가 성공했다면 음수 사이클이 있다.
	if (updated) upper.clear();
	return upper;
}

시간 복잡도

가장 바깥쪽 for 문 |V| 번, 안의 두 for문은 모든 간선을 순회하므로 O(|E|) 번 수행.

전체 시간 복잡도는 O(|V||E|)

실제 경로 계산