[알고리즘] 플로이드 와샬 알고리즘

정의 모든 정점에서 모든 정점으로의 최단 경로를 구하는 최단 경로 알고리즘이다. 거쳐가는 기준을 최단거리를 구한다는 특징이 있다. 코드 import math INF = math.inf def floyid(graph): for k in range(len(graph)): for i in range(len(graph)): for j in range(len(graph)): if graph[i][k] + graph[k][j] < graph[i][j]: graph[i][j] = graph[i][k] + graph[k][j] print(graph) _graph = [ [0, 5, INF, 8], [7, 0, 9, INF], [2, INF, 0, 4], [INF, INF, 3, 0] ] floyd(_graph)
알고리즘/최단경로 2021. 10. 24. 20:50

[알고리즘] 다익스트라 알고리즘

정의 특정한 정점으로부터 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 음의 간선은 포함시킬 수 없다. 활용 현실 생활에서 많이 사용되는 알고리즘으로 인공위성 GPS 등이 있다. 코드 시간 복잡도 O(N * log N)를 가지는 코드이다. import heapq import math def dijkstra(graph, start): distances = {node : math.inf for node in graph} distances[start] = 0 queue = [] heapq.heappush(queue, [distances[start], start]) while queue: curr_distance, curr_dest = heapq.heappop(queue) if distances[c..
알고리즘/최단경로 2021. 10. 24. 20:47