다익스트라

플로이드-워셜(Floyd-Warshall)? 플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다. 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다. 구현 설명 플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와..

다익스트라(Dijkstra)? 다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다. 특징 그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를..