대표적인 최단 거리 알고리즘

• 다익스트라 알고리즘
• 벨만 포드 알고리즘
• 플로이드 와샬 알고리즘

최단거리 알고리즘은 대표적으로 3가지가 있는데, 각각의 알고리즘마다 시간복잡도, 사용가능 상황 등의 차이점이 조금씩 있다.

다익스트라 (Dijkstra algorithm)

제한사항 : 모든 가중치가 음이 아닌 값을 가지고 있어야 함.
결과 : 한 정점에서 다른 모든 정점의 최단거리를 알 수 있음.
시간복잡도 : O(E * logV)

음의 가중치를 포함하지 못하는 이유

벨만 포드와의 차이점

다익스트라는 현재까지 방문한 정점들 중에서 거리가 최소인 정점을 고르고 나면, 더 이상 이 정점에 대해서 업데이트를 해주지 않는다. 그렇기 때문에 간선에 음의 가중치가 포함되어 있다면, 전에 골랐던 최소 정점을 업데이트 해줘야 하는 상황이 발생하므로 다익스트라는 음의 가중치를 포함할 수가 없다.

벨만 포드 알고리즘과의 큰 차이점 간선에 음의 가중치를 포함시킬 수 없다는 점이다.

그림으로 보기

코드로 보기

다익스트라 문제 풀어보기

$if(distance[v] > c(u, v) + distance[u])$

struct Node {
	int next;
    int weight;
};

struct compare {
	bool operator()(const Node& n1, const Node& n2) {
    	return n1.weight > n2.weight;
    }
};


void dijkstra() {
	vector<vector<Node>> graph = make_graph(edges, V);
	
	priority_queue<Node, vector<Node>, compare> min_node;
	vector<int> distance(V, INF);
	vector<bool> check(V);

	distance[K] = 0;
	min_node.push(Node(K, 0));

	while (!min_node.empty()) {
		Node top = min_node.top();
		min_node.pop();

		if (check[top.next]) continue;
		check[top.next] = true;

		for (auto i : graph[top.next]) {
			if (check[i.next]) continue;

			if (distance[i.next] > top.weight + i.weight) {
				distance[i.next] = top.weight + i.weight;
				min_node.push(Node(i.next, top.weight + i.weight));
			}
		}
	}

	for (auto d : distance) {
		if (d == INF) {
			cout << "INF\n";
		}
		else {
			cout << d << "\n";
		}
	}
}

벨만 포드 (Bellman Ford algorithm)

제한사항 : graph에 음의 길이를 가지는 cycle이 없어야 함.
결과 : 한 정점에서 다른 모든 정점의 최단거리를 알 수 있음.
시간복잡도 : O(VE)

다익스트라와의 차이점

• 음의 간선이 있어도 사용할 수 있다.
• 시간복잡도가 O(VE)로 다익스트라보다 느리다.

그림으로 보기

코드로 보기

벨만 포드 문제 풀어보기

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

struct Edge {
	int u;
	int v;
	int cost;
};

struct Node {
	int next;
	int weight;

	Node(int _next, int _weight) { next = _next; weight = _weight; }
};

vector<vector<Node>> make_graph(vector<Edge>& edges, int N) {
	vector<vector<Node>> graph(N);

	for (auto edge : edges) {
		graph[edge.u].push_back( Node(edge.v, edge.cost) );
	}

	return graph;
}

void bellman_ford(vector<Edge>& edges, int N) {
	vector<vector<Node>> graph = make_graph(edges, N);
	vector<int> distance(N, INF);
	queue<int> q;

	q.push(0);
	distance[0] = 0;

	// 음의 cycle을 가지는지 판단하기 위해 N - 1번이 아닌 N번 돌음.
	for (int iter = 0; iter < N; iter++) {
		if (q.empty()) {
			break;
		}

		int size = q.size();
		vector<bool> node_distance_update(N);

		for (int i = 0; i < size; i++) {
			int front = q.front();
			q.pop();

			for (auto node : graph[front]) {
				if (distance[node.next] > distance[front] + node.weight) {
					distance[node.next] = distance[front] + node.weight;
					
					if (!node_distance_update[node.next]) {
						node_distance_update[node.next] = true;
						q.push(node.next);
					}
				}
			}
		}
	}

	if (!q.empty()) {
		cout << "-1";
	}
	else {
		for (int i = 1; i < N; i++) {
			int curr = distance[i];

			if (curr == INF) {
				cout << "-1\n";
			}
			else {
				cout << curr << "\n";
			}
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;

	vector<Edge> edges(M);
	for (auto& i : edges) {
		cin >> i.u >> i.v >> i.cost;
		i.u--;   i.v--;
	}

	bellman_ford(edges, N);

	return 0;
}

플로이드 와샬 (Floyd Warshall)

제한사항 : grpah에 음의 cycle이 없어야 함.
결과 : 모든 정점에서 다른 모든 정점의 최단거리를 알 수 있음.
시간복잡도 : O(N3)

그림으로 보기

작성 중

코드로 보기

작성 중