최단경로

최단 경로

다익스트라 알고리즘 최소 비용을 구해야 할 때 사용 가능 한 지점에서 다른 특정 지점까지의 최단 경로 구해야 할 경우에 사용 가능 음의 간선이 없을 때 정상 동작함 (현실에는 음의 간선의 길이 없어서 GPS의 기본 알고리즘으로 사용됨) 그리디 알고리즘 -> 매번 가장 비용이 적은 노드를 선택해 과정을 반복함 동작 원리 dist[] 에 비용 저장, INF로 초기화 되어 있음 출발 노드 설정, 최단 거리 초기화 (dist[] INF로 초기화) 출발 노드를 방문한 노드로 체크하기 출발 노드와 연결되어 있고 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택, 방문했다고 체크 이 노드에서 다른 노드로 가는 비용을 계산해 dist[] 갱신 3,4 과정을 반복 구현 방법 동작 원리대로 구현하기 - 시간 복잡..