Dijkstra algorithm

시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련한다.
1. 최소 비용을 저장할 공간은 모두 큰 값으로 초기화합니다. 직전 노드를 저장할 공간도 INF로 초기화합니다.
2. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 합니다.
해당 노드를 통해 방문할 수 있는 노드 중, 즉 아직 방문하지 않은 노드 중 현재까지 구한 최소 비용이 가장 적은 노드를 선택합니다.
1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신합니다.
2. 이때 직전 노드도 같이 갱신합니다.
노드 개수에서 1을 뺀 만큼 반복합니다.

#include <tuple>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();
const int MAX_NODES = 100;
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];

vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>> edges){
	//그래프 및 방문 여부 초기화
	for(int i=0; i<MAX_NODES; ++i){
		fill_n(graph[i], MAX_NODES, INF);
		visited[i] = false
	}
	//간선 정보 그래프로 표현
	for (const auto &[from, to, weight] : edges){
		graph[from][to] = weight;
	}
	//시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
	vector<int> distances(numNodes, INF);
	distances[start] = 0;
	
	for(int i=0; i<numNodes - 1; ++i){ 
		int minDistance = INF;
		int closestNode = -1;
		
		//최소 거리 노드 찾기
		for(int j = 0; j < numNodes; ++j){
			if(!visited[j] && distances[j] < mindistance) {
				minDistance = distances[j];
				closestNode = j;
			}
		}
		
		visited[closestNode] = true;//찾은 노드 방문처리
		// 인접 노드에 대한 거리 업데이트	
		for(int j = 0; j < numNodes; j++) {
			int newDistance = distances[closestNode] + graph[closestNode][j];
			if (!visited[j] && graph[closestNode][j] != INF && newDistance < distances[j]){
				distances[j] = newDistance;
			}
		}
	}
	return distances;
}

Bellman-ford algorithm

음의 가중치가 있는 경우에도 노드 갯수 만큼 반복을 통해 최소 비용을 찾을 수 있다는 것이 포인트, 하지만 음수 간선의 순환이 있다면 음의 무한대로 비용이 발생

시작 노드를 설정한 다음 시작 노드의 최소 비용은 0, 나머지 노드는 INF로 초기화합니다. 이후 최소 비용을 갱신할 때 직전 노드도 갱신합니다.
노드 개수 - 1 만큼 다음 연산을 반복합니다.
1. 시작 노드에서 갈 수 있는 각 노드에 대하여 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신합니다. 최소 비용을 갱신할 때, V의 직전 노드 값도 같이 갱신합니다.
과정 2-1을 마지막으로 한 번 더 수행하여 갱신되는 최소 비용이 있는지 확인합니다. 만약 있다면 음의 순환이 있음을 의미합니다.

#include <limits>
#include <tuple>
#include <vector>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<int> solution(int num_vertices, vector<tuple<int,int,int>> edges,int source){
	vector<vector<pair<int,int>>> graph(num_vertices);
	
	//간선 정보를 활용해서 인접 리스트를 생성
	for (auto &edge : edges){
		int from, to, weight;
		tie(from, to, weight) = edge;
		graph[from].emplace_back(to,weight);
	}
	
	//현재까지 구한 최소 비용을 INF로 설정 (시작 노드는 제외)
	vector<int> distance(num_vertices, INF);
	distance[source] = 0;
	// 정점의 개수 -1만큼 최소 비용을 갱신
	for(int i = 0; i < num_vertices - 1; ++i){
		for(int u = 0; u<num_vertices; ++u){
			for(const auto &[v, weight] : graph[u]){
				if(distance[u]+weight<distance[v]){
					distance[v] = distance[u] + weight;
				}
			}
		}
	}
	//음의 순환이 있는 지 확인
	for(int u =0 ;u<num_vertices;++u){
		for(const auto &[v,weight]:graph[u]){
			if(distance[u] + weight <distance[v]){
				return vector<int>(1,-1);
			}
		}
	}
	return distance;
}