목록Bellman-Ford Algorithm (1)

맛있는감귤

BOJ : 11657 타임머신

문제 : https://www.acmicpc.net/problem/11657최단거리를 찾는 문제같은데 타임머신이 있거나 시간을 역행하는 문제, 음수 가중치가 존재하는 대다수의 문제는 벨만-포드 알고리즘으로 해결가능합니다.다익스트라 알고리즘 같은 경우 해당 노드에 존재하는 간선을 보고 가중치가 가장 작은 값을 선택하게 됩니다.그렇기 때문에A -> B -> C / A -> C 의 루트에서1 5 -4 1 3의 값을 가질 때 노드 A의 간선의 가중치 5와 3만을 비교하기 때문에 원하는 답을 도출할 수 없습니다.왜냐하면 1 -> 5 -> -4이 더 최단 거리가 되기 때문이죠.그렇기 때문에 간선을 비교하고 또 노드의 개수-1만큼 또 비교를 해주면 됩니다. (도착지 노드까지 가는 간선은 전체 노드개수를 넘지 않기 때..
알고리즘/백준 알고리즘 2017. 3. 15. 03:27
이전 Prev 1 Next 다음