다익스트라1 [알고리즘] 최단 경로 알고리즘 * 최단 경로 문제 : 가장 짧은 경로를 찾는 알고리즘 - 한 지점에서 다른 한 지점까지의 최단 경로 - 한 지점에서 다른 모든 지점까지의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현, 지점 간 연결된 도로는 그래프에서 간선으로 표현 [다익스트라 최단 경로 알고리즘] : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 방법 - 음의 간선이 없을 때 정상적으로 동작 - 그리디 알고리즘으로 분류 (매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복) - 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 바뀌지 않음 1. 출발 노드 설정 2. 최단 거리 테이블을 초기화 (자기 자신과의 거리 0, 나머지는 INF) 3. .. 2022. 11. 20. 이전 1 다음