최단경로 파이썬 Algorithm/Study 2021. 9. 24. 최단 경로 알고리즘 : 플로이드 워셜 플로이드 워셜 알고리즘 개념 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘 (↔ 다익스트라 알고리즘 : 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘) - 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. - 2차원 리스트에 최단 거리 정보를 저장한다. - 시간 복잡도 : O(N^3) - 다이나믹 프로그래밍이다. (점화식 사용) Dab = min(Dab, Dak + Dkb) A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신한다. 구현 INF = int(1e9) # 노드 개수, 간선 개수 n = int(input()) m = int(input()) #.. Algorithm/Study 2021. 9. 24. 최단 경로 알고리즘 : 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다. 다익스트라 최단 경로 알고리즘 개념 - 그래프에 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. - '음의 간선'이 없을 때 사용할 수 있다. - GPS 소프트웨어 기본 알고리즘으로 채택되곤 한다. - 그리디 알고리즘으로 분류된다. (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문) - heapq(우선순위 큐) 사용 시, 시간 복잡도 : O(ElogV) (V : 노드 개수, E : 간선 개수) 최단 거리가 가장 짧은 노드를 순차 탐색이 아니라 힙 자료구조를 사용함으로써 시간복잡도를 줄인다. 힙 자료구조를 이용하면 특정 노드까.. 이전 1 다음
