최단 경로 - 다익스트라/벨만포드/플로이드워셜

최단 경로 문제

가중 그래프에서 간선의 가중치 합이 최소가 되는 경로를 찾는 문제

종류

유형	설명	대표 알고리즘
단일 출발	하나의 출발 정점에서 나머지 모든 정점까지 최단 경로	다익스트라, 벨만-포드
단일 도착	모든 정점에서 하나의 도착 정점까지 최단 경로	다익스트라(역방향 그래프), 벨만-포드
단일 쌍	특정 정점 v1에서 v2로 가는 최단 경로	다익스트라, 벨만-포드
전체 쌍	모든 정점 쌍 사이의 최단 경로	플로이드-워셜

다익스트라 알고리즘 (Dijkstra Algorithm)

음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점에서부터 다른 모든 정점까지의 최단경로 구하는 알고리즘

특징

• 각 정점을 최대 한번씩만 방문
• 아직 방문하지 않은 정점 중 최단거리인 점을 찾아 방문해 최단거리 확정 → 반복
• 우선순위 큐나 힙 사용 → O(ElogV)의 시간복잡도

dist[s] = 0 출발점을 0으로 저장
방문하지 않은 정점 중, dist[i]가 최소인 정점 i 선택 ⇒ 최소힙에서 맨 위에 있는 정점 i 꺼냄
dist[j] = dist[i] + w로 갱신 → 최소 힙에 정점 j 삽입

구현

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

struct edge {
	int to;
	int cost;
};
struct compare {
	bool operator() (edge a, edge b) {
		return a.cost > b.cost;
	}
};

int n, m; // #node, #edge
vector<int> dist;
vector<vector<edge>> adjList;

void dijkstra(int start) {
	dist[start] = 0;

	priority_queue<edge, vector<edge>, compare> pq;
	vector<bool> visited(n + 1, false);

	pq.push({ start, 0 });

	while (!pq.empty()) {
		edge cur = pq.top();
		pq.pop();

		if visited[cur.to]) continue;
		visited[cur.to] = true;

		for (edge next : adjList[cur.to]) {
			if (dist[next.to] > cur.cost + next.cost) {
				dist[next.to] = cur.cost + next.cost;
				pq.push({ next.to, dist[next.to] });
			}
		}
	}
}

int main() {
    cin >> n >> m;
    
    adjList.resize(n + 1);
    dist.resize(n + 1, INT_MAX);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adjList[u].push_back({v, w});
    }

    int start;
    cin >> start;
    
    dijkstra(start);

    return 0;
}

벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm)

가중 그래프(음의 가중 존재)에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점에서부터 다른 모든 정점까지의 최단경로 구하는 알고리즘

특징

• 음의 가중치 가능
• 음의 사이클 존재 여부 확인 가능
• 최단거리를 구하기 위해 V-1번 E개의 모든 간선 확인
• 음의 사이클 존재 여부 확인 위해 한 번 더 E개의 간선 확인 → 이때 갱신되면 음의 사이클 가짐
• O(VE)의 시간복잡도

구현

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

struct edge {
	int from;
	int to;
	int cost;
};

int v, e; 
vector<edge> edgeList;
vector<long long int> dist;

bool BellmanFord(int start) {
	dist[start] = 0;

	//v-1번 탐색
	for (int i = 0; i < v - 1; i++) {
		for (edge e : edgeList) {
			//간선의 시작점이 탐색불가
			if (dist[e.from] == LONG_MAX) continue;

			if (dist[e.to] > dist[e.from] + e.cost)
				dist[e.to] = dist[e.from] + e.cost;
		}
	}

	//음의 사이클 검사
	bool negativeCycle = false;

	for (edge e : edgeList) {
		if (dist[e.from] == LONG_MAX) continue;

		if (dist[e.to] > dist[e.from] + e.cost) {
			negativeCycle = true;
			break;
		}
	}

	return negativeCycle;
}

int main() {
    cin >> v >> e;
    
    edgeList.resize(e);
    dist.resize(v + 1, LLONG_MAX);

    for (int i = 0; i < e; i++) {
        cin >> edgeList[i].from >> edgeList[i].to >> edgeList[i].cost;
    }

    int start;
    cin >> start;
    bool hasNegativeCycle = BellmanFord(start);

    return 0;
}

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

전체 쌍 최단 경로 문제
V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 모든 정점 사이의 최단경로 구하는 알고리즘

특징

• 순환이 없다는 가정하에 음의 가중치 가능
• O(V^3)의 시간복잡도

구현

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

int n, m; // #node, #edge
vector<vector<int>> dist;

void FloydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == k || k == i) continue;
				if (dist[i][k] == INT_MAX || dist[k][j] == INT_MAX) continue;

				if (dist[i][j] > dist[i][k] + dist[k][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
}

int main() {
    cin >> n >> m;
    
    dist.assign(n + 1, vector<int>(n + 1, INT_MAX));

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    FloydWarshall();

    return 0;
}