그래프

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍를 활용한 최단 경로(Shortest path) 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다익스트라 알고리즘이 다이나믹 프로그래밍을 활용하는 이유는 '최단 거리는 다양한 루트가 존재하기 때문'이다. 그렇기에 기존에 하나의 최단 거리를 구할 때 까지 모든 루트를 그대로 사용한다. 아래의 그래프에서 1에서 다른 정점으로 가는 최단 거리를 구한다고 해보자. 1에서 각 정점으로 한 번에 가는 최단 거리는 각 3, 6, 7이다. 이 때 한 번에 가는 것이 아닌 2를 거쳐 정점 3과 정점 4로 간다면 3 > 1과 3 > 1 >..

플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 문제들이 있다. 이 경우 플로이드 와샬 알고리즘을 사용하면 쉽게 모든 정점의 최단 거리를 구할 수 있다. 플로이드 와샬을 기본적으로 DP를 기반으로 진행된다. 플로이드 와샬 알고리즘의 주요 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 위 와 같은 그래프가 존재한다고 가정하자.이 때 각 정점에서 다른 정점으로 가는 비용을 이차원 배열로 정리하면 아래와 같다. 해당 테이블이 의미하는 바는 '현재까지의 최단 거리'이다. 해당 테이블을 통해 지나치는 정점으로 다른 정점으로 가는 테이블을 그릴 것이다. 1. 노드 1을 거쳐가는 경우 노드 1을 거쳐가는 경우는 노드 2와 노드 3이다. 이를 테이블로 나타내면 아래와 같다..