알고리즘/최단 경로
[이코테] 실전 문제
최단 경로 알고리즘은 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있는데 이를 각각 구현하는 포스트는 다음에 올리겠다. 한 지점에서 특정 지점까지의 최단 경로를 구할 때에는 다익스트라를, 모든 지점에서 모든 지점까지의 최단 경로를 구할 때는 플로이드 워셜을, 다익스트라와 같은 경우지만 음의 가중치를 가진 간선이 존재할 경우 벨만 포드 알고리즘을 사용하면 된다. 미래 도시 방향이 없고 가중치가 없는 그래프로 1번 회사에서 K번 회사로, K번 회사에서 X번 회사로 가는 최단 경로를 구하는 문제였다. 나는 이 문제를 1번부터 K번, K번부터 X번까지의 최단 경로를 다익스트라를 이용해 구한 후 두 개의 값을 더해서 풀었는데 책에서는 전형적인 플로이드 워셜 유형의 문제라고 했다. 노드와 간선의 개수가 100..
