코딩테스트 관련 내용정리 (4)

최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘을 의미한다. - '길찾기' 문제라고도 불림 - 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. - 그리디 알고리즘으로 분류된다. (1) 출발 노드를 설정한다. (2) 최단 거리 테이블을 초기화 한다. (3) 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. (4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. (5) (3),(4)번을 반복한다. - '각 노드에 대한 현재까지의 최단거리' 정보..