CS/Data Structure1 Dijkstra with Python 소개 다익스트라는 최단경로 알고리즘 중에서도 대표적인 예시라고 할 수 있다. 하나의 시작 정점에서부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘이다. (다만 weight값이 음수이지만 않는다면) 배경 최단 경로 알고리즘은 graph 자료구조를 사용하며, node와 edge를 이용해 실제 거리를 나타낸다. 1. 출발 노드, 도착 노드 설정 2. edge에 값을 부여 3. 출발 노드부터 시작해 방문하지 않은 인접 노드 방문, 거리를 계산하고, 현재거리와 비교해 더 작은 값을 넣는다. 4. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 5. 해당 노드를 거쳐 특정 노드로 가는 경우를 고려해 최소 비용 갱신 6. 4~5를 반복 ex) 이런 그래프가 있다 가정하자 자 그럼 표를 만들어서 보자 0 2 .. 2023. 2. 26. 이전 1 다음 728x90