Floyd - Warshall 알고리즘 이전에 각각 살펴봤던 Dijkstra, Bellman - Ford 알고리즘은 시작 지점이 존재하고, 해당 지점에서 각 노드로의 최단 경로를 구하는데 사용하는 알고리즘이다. Floyd - Warshall 알고리즘은 모든 노드에 대해서 각 노드에 대한 최단 거리를 구하는 알고리즘이다. 쉽게 말하자면 모든 노드에 대하여 Dijkstra나 Bellman - Ford를 돌려보았다고 생각하면 좋다. 다만 구현 방법은 순수 DP를 사용한다는 것이 차이점이다. Floyd - Warshall 알고리즘 역시 음의 가중치가 존재해도 사용이 가능하며, Bellman - Ford와 동일하게 음수 사이클이 존재한다면 사용할 수 없다. Floyd - Warshall 알고리즘의 원리 DP를 사..

들어가며 이전에 보았던 다익스트라는 하나의 정점에서 다른 정점까지의 모든 최단 경로를 구하는데 $O((V + E) \log V)$라는 강력한 성능을 보여주었다. 하지만 문제점이 있는데 음의 가중치가 존재하는 경우 제대로 된 값을 구할 수 없다는 것이다. 이는 그리디 알고리즘의 허점과도 연관되는데 아래와 같은 간단한 그래프를 통해 알아보자. 해당 그래프에서 1부터 시작한다고 가정할 때 최단 경로는 5가 된다. 하지만 다익스트라를 사용할 시 6이 되는데 그리디하게 1번과 인접한 곳의 가중치가 각각 7, 6으로 가중치가 더 적은 6을 먼저 갱신해버리기 때문이다. 이러한 문제를 해결하기 위해서는 이미 갱신해버린 값이어도 다시 한번 검사를 해보는 방식이 필요한데 이런 방식을 구현한 알고리즘이 Bellman-For..

최단 거리 최단 거리 또는 최단 경로(Shortest Path)는 일반적으로 그래프상에서 이루어지는 개념이다. 그래프에서 한 노드를 기준으로 하여 다른 노드까지 이동하는데 걸리는 시간이 가장 적은 경로가 최단 경로 또는 최단 거리가 될 것이다. 이때 이동하는데 걸리는 시간을 수치적으로 나타낸 것이 가중치(weight)이고 최단 경로 문제는 다음과 같이 정의할 수 있을 것이다. 어떤 노드 $V_i$ 에서 다른 노드 $V_j$ 로 이동할 때 드는 가중치 $W$가 최소가 되는 경로를 구하는 문제 활용처와 방법론 최단 경로 알고리즘의 활용은 매우 무궁무진하다. 일상적으로 가장 가까이서 찾아볼 수 있는 최단 경로 알고리즘의 활용처는 네비게이션이 될 것이다. 거리의 교차점을 하나의 노드로, 도로를 간선으로 추상화한..