muntari Log muntari Log

최단 경로 (Shortest Path) 두 노드 사이에 존재할 수 있는 모든 경로 중 거리가 가장 짧은 경로를 말한다. 비가중치 그래프에서는 경로 중 엣지의 수가 가장 적은 것이 최단 경로이며 가중치 그래프에서는 보통 엣지의 가중치의 합이 가장 적은 경로가 최단 경로가 된다. 최단 경로 알고리즘 주어진 그래프에서 두 노드 사이에 가장 짧은 경로를 구하는 방법을 최단 경로 알고리즘이라 부른다. 이 최단 경로 알고리즘은 단 하나의 방법으로 구성되어 있지 않고 여러 방법이 존재한다. 엣지의 방향이 있는지, 가중치가 있는지, 음수 엣지가 존재하는지, 싸이클이 존재하는 지 등등 다양한 그래프 특징에 ㅏ따라 많은 방법이 존재한다. 대표적으로 두 개의 최단 경로 알고리즘인 BFS와 Dijksatr 알고리즘을 알아보자..