Leta Learns

최단 경로 알고리즘 (Shortest Path) 그래프에는 어떤 정점에서 다른 정점으로의 사이를 잇는 최단 경로를 구하는 알고리즘이 존재한다. ( != MST ) MST : N-1개의 간선으로 최소 가중치 트리 만듦 그래프 내의 모든 간선의 가중치가 0 이상인 경우 => Dijkstra 알고리즘을 이용한다. 그래프가 음수 가중치 간선을 포함하는 경우 => Bellman-Ford 알고리즘을 이용한다. Dijkstra 알고리즘 출발 정점으로부터 가장 가까운 아직 방문하지 않은 정점을 찾고, 다른 모든 정점까지의 거리에 대해서 선택된 정점을 지나서 가는 경우와, 직접 가는 경우 중 최솟값으로 최단 거리를 갱신해가면서 가장 가까운 정점을 하나씩 방문한 정점 집합에 추가하는 방식으로 최단 경로를 갱신. (음의 간..