최단 경로, 개선된 다익스트라 알고리즘
📌방법 2. 개선된 다익스트라 알고리즘 시간 복잡도: O(ElogV), V=노드의 개수, E=간선의 개수힙 자료구조 사용특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음(로그 시간) 방법 1에서 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용하는 방식으로 대체 📌개선된 다익스트라 알고리즘 소스 코드import heapqimport sysinput = sys.stdin.readlineINF = int(1e9) # 무한, 10억# 노드의 개수, 간선의 개수 입력받기n, m = map(int, input().split())# 시작 노드 번호 입력받기start = int(input())# 각 노드에 연결되어..
코딩테스트
2024. 11. 4. 21:00