[C++] 다익스트라와 플로이드 와샬 알고리즘

차이

• 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최소 거리
  • 매번 가장 적은 비용을 가진 노드를 하나씩 꺼내, 가장 적은 비용을 하나씩 선택함.
• 플로이드 와샬 : 모든 시작점에서 에서 다른 모든 정점까지의 최단 거리
  • 애초에 거쳐가는 정점을 하나씩 다 설정해서 직접 확인함. 거쳐가는 정점을 기준으로 최단 거리를 구성함.

 

우선순위 큐를 이용한 다익스트라

• 우선순위큐 + BFS의 형태를 가진다.
• 각 정점까지의 최단거리를 저장하는 배열 dp[]를 유지하고, 정점을 방문할 때마다 인접한 정점을 모두 검사한다.

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

const int INF = 1e9;
int V, E, start;

void dijkstra(int start, vector<vector<pair<int, int>>>& graph) {
	// 노드별 거리 저장용
	vector<int> dist(V+1, INF);
    // 우선순위 큐로 cost가 낮은 순으로 정렬됨
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
	dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
    	auto [cost, now] = pq.top();
        pq.pop();
        
        if (dist[now] < cost) continue;
        
        // 현재 노드에서 이어진 다음 노드 탐색
        for (const auto& [next, weight] : graph[now]) {
        	// 여태 기록해놨던 거리보다 더 적은 비용으로 갈 수 있으면 큐에 push
        	if (dist[next] > cost + weight) {
            	dist[next] = cost + weight;
                pq.push({dist[next], next);
            }
        }
    }
    
    // 결과 출력
    for (int i=1; i<=V; i++) {
    	if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << '\n';
    }
}

int main() {
	cin >> V >> E;
    vector<vector<pair<int, int>>> graph(V+1);
    
    for (int i=0; i<E; i++) {
    	int a, b, cost;
        cin >> a >> b >> cost;
        graph[a].push_back({cost, b});
        // 양방향일 경우 b->a도 고려해주어야 함.
    }
    
    cin >> start;
    dijkstra(start, graph);
    
    return 0;
}

 

모든 쌍 간의 최단거리 구하는 플로이드 와샬

경유점이라는 개념을 알아야 한다.

두 정점 u, v를 잇는 경로가 있다고 할 때, 이 경로는 시작점 u, 끝점 v를 가진다. 이 외에 이 경로는 다른 정점들을 지나쳐서 갈 수도 있다.

[u, n, m, p, v]도 u와 v를 잇는 경로이다. 여기서 [n, m p] 가 경유점이 된다.

 

이런 식으로 경유점을 이용해서 더 짧은 거리를 찾는 방법이 플로이드 와샬이다.

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

const int INF = 1e9;
int V, E;

int main() {
	cin >> V >> E;
    vector<vector<int>> dist(V+1, INF);
    
    // 자기 자신까지의 거리는 0
    for (int i=1; i<=V; i++) dist[i][i] = 0;
    
    for (int i=0; i<E; i++) {
    	int a, b, cost;
        cin >> a >> b >> cost;
        dist[a][b] = c;
    }
    
    // 플로이드 와샬 알고리즘
    for (int k=1; k<=V; k++) {
    	for (int i=1; i<=V; i++) {
        	for(int j=1; j<=V; j++) {
            	// i -> k에 갈 수 있고, k -> j로 갈 수 있으면
            	if (dist[i][k] != INF && dist[k][j] != INF) {
                	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    // 결과 출력
    for (int i=1; i<=V; i++) {
    	for (int j=1; j<=V; j++) {
        	if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }
}