그래프 최단경로 알고리즘 정리

다익스트라 (Dijkstra)

시작 정점에서, 다른 모든 정점까지의 최단거리를 $O(E\log V)$에 구할 수 있다. 모든 간선을 한 번씩 확인하기 때문에 인접 리스트로 구현. 최단거리가 여러 번 갱신된 경우 (cost > dist[cur]) 스킵. cost가 낮은 간선부터 확인.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int dijkstra(int start, int end) {
    fill(dist, dist+MAX, INF);
    dist[start] = 0;
    pq.emplace(0, start);
    while (!pq.empty()) {
        auto [cost, cur] = pq.top();
        pq.pop();
        if (cost > dist[cur]) continue;

        for (auto& [ncost, next] : adj[cur]) {
            if (dist[next] > dist[cur] + ncost) {
                dist[next] = dist[cur] + ncost;
                pq.emplace(dist[next], next);
            }
        }
    }
    return dist[end];
}

벨만 포드 (Bellman - Ford)

시작 정점에서, 다른 모든 정점까지의 최단거리를 $O(EV)$에 구할 수 있다. 다익스트라 알고리즘과는 달리 음의 간선이 존재해도 주어진 시간 안에 최단거리를 구할 수 있다. 최단경로는 아무리 길어도 $V-1$개의 간선을 포함하고 있을 것이다. 따라서 간선 완화를 $V-1$번 진행한다. 만약 $V-1$번 진행 이후에도 최단거리가 짧아진다면, 이는 음의 사이클을 가지고 있는 것이다.

int start = 0;
fill(dist, dist+MAX, INF);
dist[start] = 0;
bool neg = false;

for (int k = 0; k < N; k++) {
	for (int i = 0; i < N; i++) {
		if (dist[i] == INF) continue;
		for (auto p : adj[i]) {
			auto [cost, next] = p;
			if (dist[next] > dist[i] + cost) {
				dist[next] = dist[i] + cost;
				if (k == N-1) neg = true;
			}
		}
	}
}

플로이드 와샬 (Floyd - Warshall)

모든 정점에서, 다른 모든 정점까지의 최단거리를 $O(N^3)$ 에 구할 수 있다. 반복문 순서에 유의한다. $dist(i, j)$와 $dist(i, k) + dist(k, j)$를 비교하는데, $k$를 고정시켜놓고 $i, j$를 움직인다. 다이나믹 프로그래밍의 일종.

while (r--) {
	int a, b, c;
	cin >> a >> b >> c;
	dist[a-1][b-1] = c;
	dist[b-1][a-1] = c;
}

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		if (!dist[i][j]) dist[i][j] = 1e9;
		if (i == j) dist[i][j] = 0;
	}
}

// i -> j vs i -> k -> j
for (int k = 0; k < n; k++) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
}