항해 99 //백준 11657 //타임머신//벨만 포드(Bellamn- Ford) 알고리즘

https://www.acmicpc.net/problem/11657

 

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

벨만 포드(Bellamn- Ford) 알고리즘

음수 가중치가 있고 음수 사이클이 있는 그래프에서 단일 출발점 최단 경로를 구하는 알고리즘

(음수 사이클이 존재하는 것도 판별할 수 있음 -> 만약 타임머신, 블랙홀 , 과거로 돌아갈 수 있다는 워딩이 있다면 벨만 포드 알고리즘을 사용해야하나 생각해 보기)

 

원리 

모든 간선을 반복적으로 확인하며 최단 경로를 갱신

1. 초기화: 출발 노드에서 출발노드까지의 거리는 0으로 설정, 나머지 노드들은 무한대로 초기화

2. 최단 경로 갱신 : 모든 간선을 V-1번 반복 검사, 현재 경로가 기존 경로보다 짧다면 해당경로로 완화함

3. 음수 사이클 확인: 최단 경로가 확인된 후에도, 다시 모든 간선을 검사하여 최단 경로가 더 짧아지는 경로가 있다면 이는 음수 사이클이 존재한다는 의미

 

#include <iostream>
#include <tuple>
#include <vector>
#include <limits>
using namespace std;

const long long INF = numeric_limits<long long>::max();
void solve(int n, int m, vector<tuple<int, int, int>>& edges)
{
	vector<long long> dist(n + 1, INF);//dist = (INF, INF, INF, INF,INF, INF)
	//그래프는 1번부터 n+1까지 사용~dist[0]은 사용하지 않음
	dist[1] = 0;//시작점에서 시작점까지의 거리 0으로 초기화 //dist = (INF, 0, INF, INF,INF, INF)
	
    // 벨만-포드 알고리즘: 모든 간선에 대해 최대 (n-1)번 반복하며 각 정점에서 다른 정점으로의 최단 거리를 갱신
    for (int i = 0; i < n-1; i++)
	{
		for (auto [u,v,w] : edges)
		{
			//dist = (INF, 0, INF, INF,INF, INF) 시작점에서 
			// 새로 계산된 거리(dist[u]+w가 기존값(dist[v]보다 짧아지면
			if (dist[u] != INF && dist[u] + w < dist[v])
			{
				dist[v] = dist[u] + w;//값 교체
			}
		}
	}
	for (auto [u, v, w] : edges)
	{
		// 간선을 한 번 더 탐색했을 때 최단 거리가 갱신되었다는 건 음수 사이클 존재한다는 의미
        if (dist[u] != INF && dist[u] + w < dist[v])
		{
			cout << -1 << endl;
			return;
		}
	}
    
    //i=2: 시작점(1번 정점)에서 다른 정점으로의 거리를 출력하므로, 1번 정점은 제외
	for (int i = 2; i <= n; i++)
	{
		if (dist[i] == INF) cout << -1 << endl; //도달할 수 없는 경우 -1 출력
		else cout << dist[i] << endl;//최단 거리 출력
	}
}

int main()
{
	int n, m;
	cin >> n>> m;

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a>>b>>c;
		edges.emplace_back(a, b, c);
		
	}
	/*
	for (auto e : edges)
	{
		cout << "From: " << get<0>(e) << ", To: " << get<1>(e) << ", Weight: " << get<2>(e) << endl;
	}*/
	solve(n, m, edges);

	return 0;
}