백준 11675 타임머신

해당 문제의 경우 벨만포드 알고리즘을 사용해 푸는 문제이다.
처음에는 최단 경로만 보고 단순히 bfs를 사용하려다 각 간선의 가중치가 다 다르다는 것에 다익스트라와 벨만포드를 생각하게 되었다.
하지만 음수 간선이 존재하기에 다익스트라는 사용할 수 없었다.
그래서 벨만포드를 사용해 해당 문제를 풀게 되었다.

벨만포드란

벨만포드 알고리즘의 경우 최단경로를 찾는 알고리즘이다. 매 단계마다 모든 간선을 전부 확인하면서 모든 노드 간의 최단거리를 구해가야한다.
그렇기에 시간복잡도는 O(VE) (V: 노드 수, E: 에지 수)가 된다.

간단하게 말하면 이렇고 코드에 적용할때는
각 엣지를 저장하는 배열 하나와
각 노드의 최단 길이를 저장하는 배열 하나가 필요하다.
이때 시작노드의 경우 최단길이를 0으로 놓고 나머지는 Infinity로 놓고 하면 된다.

아래와 같이 코드를 짤 수 있을것이다.

//distTo는 최단 길이를 저장하는 배열
function relax(source, target, weight, cycle)
{
	if(distTo[source] != Infinity && distTo[target] > distTo[source] + weight)
    {
    	distTo[target] = distTo[source] + weight;
    }
}

for V회 반복
	for 간선 갯수 반복
    	//엣지를 하나 꺼내
    	relax(source, target, weight, cycle) //이때 cycle의 경우 V회 반복 할때 relax 하는지 체크하여 negative cycle을 체크하는 용도이다.

벨만포드의 경우 음의 사이클이 존재하면 안된다. 그래서 V번째에 relax를 하게 되면 음의 간선이 있다고 판단하게 된다. 그 근거는 최단 거리의 엣지 개수는 최대 V-1개 이기 때문에 V-1번째에 최단경로를 다 찾을 수 있고 만약 V번째에 최단경로가 업데이트 되게 되면 이는 음의 사이클이 있다고 판단할 근거가 된다.
해당 문제의 경우에도 음의 사이클이 존재할때는 -1을 출력하게 되어있다.
만약 V번째에 음의 사이클이 존재하지 않게 되면 distTo에서 각 노드까지의 최단거리를 출력해주면 된다.