heap1 [알고리즘] 최단 경로 알고리즘 (다익스트라, 플로이드 워셜) 🧩 최단 경로 알고리즘 최단 경로 알고리즘: 가장 짧은 경로를 찾는 알고리즘 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 [그래프] 노드(각 지점) / 간선(지점 간 연결된 도로) 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작 그리디 알고리즘 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 ✔️ 동작 과정 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 위 과정에서 3번, 4번 .. 2022. 10. 25. 이전 1 다음 반응형
