최단경로3 최단거리 개념 및 문제 접근 방법 0. 개요 - 최단 거리 알고리즘은 그래프 탐색 알고리즘 중 하나이다. - 최단 거리 알고리즘의 종류와 개념 그리고 문제 접근 방법에 대해서 알아보자. 1. 최단 거리 개념과 종류 a) 최단 거리의 의미 - 최단 거리 문제에서 최단 거리는 다음 2가지 경우 중 하나에 해당한다. → 지나온 간선(edge)의 개수가 가장 적은 경로를 찾는 경우 (가중치가 없는 그래프) → 지나온 간선(edge)의 가중치(weight) 합이 가장 작은 경로를 찾는 경우 (가중치가 있는 그래프) b) 최단 거리의 종류 - 최단 거리 문제는 기본적으로 시작점과 도착점이 주어진다. - 시작점과 도착점을 기준으로 최단 경로(간선의 개수 또는 간선 가중치의 합)를 구하는 것이 문제의 핵심이다. - 시작점과 도착점의 구성 방식에 따라서.. 2022. 7. 18. Advanced Algorithm - 최단경로(Shortest Path) 알고리즘(2) * 해당 포스팅은 최단경로(Shortest Path) 알고리즘(1)과 이어지는 내용입니다. 1. 파이썬을 이용한 다익스트라 알고리즘 구현(우선순위 큐 활용) a) heapq 라이브러리를 활용하여 우선순위 큐 사용하기 # heapq 라이브러리를 이용한 우선순위 큐 작성 import heapq queue = [] # heappush(자료구조, 삽입할 데이터) - queue라는 자료구조에 MinHeap 형태로 데이터를 삽입한다. # 거리를 key로 노드명을 value로 사용한다. heapq.heappush(queue, [2,'A']) heapq.heappush(queue, [5,'B']) heapq.heappush(queue, [1,'C']) heapq.heappush(queue, [7,'D']) [테스트 및.. 2020. 9. 28. Advanced Algorithm - 최단경로(Shortest Path) 알고리즘(1) 1. 최단경로 알고리즘이란? - 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘이다. - 가중치 그래프(weighted graph)에서 간선(edge)의 가중치 합이 최소인 경로를 찾는 것이 목적이다. 2. 최단경로 문제의 종류 a) 단일 출발 및 단일 도착(Single-source & single-destination shortest path problem) - 그래프 내의 특정 노드 A에서 출발하여 또 다른 특정 노드 B에 도착하는 가장 짧은 경로를 찾는 문제 b) 단일 출발(Single-source shortest path problem) - 그래프 내의 특정 노드 A와 A를 제외한 그래프 내 모든 노드 각각의 가장 짧은 경로를 찾는 문제 c) 전체 쌍(all-pair) 최단경로 - 그래.. 2020. 9. 27. 이전 1 다음
