최단 경로
📌최단 경로가장 짧은 경로길 찾기 문제라고도 불림보통 그래프를 이용해 표현 최단 거리 알고리즘 3가지: 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용 📌다익스트라 최단 경로 알고리즘그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘매번 가장 비용이 적은 노드를 선택해서 다음 과정을 반복1. 출발 노드 설정2. 최단 거리 테이블 초기화3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신5. 3, 4번 반복 각 노드에 대한 현재까지의 최단 거리 정보..
코딩테스트
2024. 11. 3. 12:43