Shortest Path Algorithm 길 찾기 문제라고도 불리는 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 한 지점에서 다른 지점까지의 최단 경로를 구하는 다익스트라 알고리즘과 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 플로이드 와샬 알고리즘에 대해 알아보자. Dijkstra Algorithm 다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해준다. 음의 간선이 없을 때 정상적으로 동작하며, 매 순간 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. 원리는 다음과 같다. 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 해당 노드를 ..
