1. 데이크스트라
시작 노드에서 특정 노드까지 가는 최소 거리를 재는 알고리즘으로,
마지막으로 방문한 노드와 연결된 것들 중 가장 작은 것을 선택후 거리를 탐색하며, 그리디 알고리즘에 해당한다.
-- 시작 노드 이외의 다른 노드까지의 거리를 무한대로 지정한다.
-- 시작노드를 선택후 방문처리 한다.
-- 시장 노드를 제외한 다른 노드들 만큼 아래를 반복한다.
----- 방문하지 않은 노드들 중 가장 거리가 짧은 노드를 선택 후 방문처리 한다.
----- 선택된 노드와 연결된 노드들(방문 X)을 순회하며, [선택된 노드까지의 거리 + 선택된 노드와 연결된 노드까지의 거리]를 기존의 거리와 비교후 작으면 업데이트 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | INF = 1e9; graph = [ [], [(1,4),(2,2),(5,3)], [(2,4),(3,3)], [(3,2),(5,6)], [(3,3),(1,5)], [(1,3),(2,6)], [] ]; # 방문하지 않은 노드들 중 가장 작은 노드 찾기 def minnode(n, d, visited): ret = [-1, INF]; for i in range(7): if ret[1] > d[i] and visited[i] == False : ret = [i,d[i]]; return ret[0]; def dijkstra(s) : visited = [False] * 7; visited[0] = True; d = [INF] * 7; # 시작지점 거리 초기화 및 방문 처리 d[s] = 0; visited[s] = True; # 시작지점에서의 거리 초기화 for i in graph[s]: d[i[1]] = i[0]; # 노드 갯수만큼 반복 # 원리가 각 노드를 거쳤을 때 이전 거리보다 작아지면 업데이트 하는거기 때문에.. for n in range(7): # 아직 방문 안한 노드 중 가장 거리가 짧은것 받아오기 s = minnode(s, d, visited); # 방문처리 visited[s] = True; # 위에서 얻은 노드를 거칠 때 거리가 작아지면 업데이트 for i in graph[s]: idx = i[1]; dist = i[0]; if visited[idx] == False: if d[idx] > d[s] + dist: d[idx] = d[s] + dist; return d[1:]; print(dijkstra(1)) | cs |
이를 리스트로 처리하는 방법도 있지만 그러면 효율성이 떨어지기에, 일부분을 우선순위 큐로 처리한다.
이렇게 할 경우 "가장 거리가 작은 노드"를 찾는데 드는 시간이 줄어든다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import heapq; INF = 1e9; graph = [ [], [(1,4),(2,2),(5,3)], [(2,4),(3,3)], [(3,2),(5,6)], [(3,3),(1,5)], [(1,3),(2,6)], [] ]; def dijkstra() : q = []; d = [INF] * 7; s = 1; d[s] = 0; # 큐에 (거리, 노드번호) 추가 # 거리 순으로 뽑아내야 하므로 우선순위 큐 사용 heapq.heappush(q,(0,s)); while q: # 큐에서 끄낸 후 현재 자리로 정함 dist, now = heapq.heappop(q); # 이미 계산된 값이 있으며 아래와 같은 경우, # 거리는 다른데 노드번호는 중복되어서 힙에 들어가 있을 때가 있음. # (5,3), (2,3) 이 큐에 들어갔을 때 (2,3) 먼저 처리된 다음에 (5,3)을 처리할 경우 if d[now] < dist : continue; # 현재 자리와 연결된 노드들 순회 for i in graph[now]: # 시작 노드에서 현재 자리까지의 거리 + 현재 자리에서 해당 노드까지의 거리 cost = dist + i[0]; idx = i[1]; # 이미 계산되어 있는 시작노드에서 해당 노드까지의 거리 보다 위 결과가 작다면 if cost < d[idx]: # 업데이트 d[idx] = cost; # 및 큐에 등록하므로써 순회할 수 있도록 처리 heapq.heappush(q, (cost, idx)); return d[1:]; print(dijkstra()); | cs |
2. 플로이드
모든 노드끼리 서로 걸리는 거리를 재는 알고리즘이다.
점화식은 아래와 같으며, 시간복잡도가 V3 이므로 노드의 갯수가 적어야 한다.
D[a][b] = min(D[a][b], D[a][k]+D[k][b])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | import heapq; INF = 1e9; graph = [ [], [(4,2),(6,4)], [(3,1),(7,3)], [(5,1),(4,4)], [(2,3)] ]; def floyd(): d = [[INF] * 5 for _ in range(5)]; # 그래프에 따라 현재 d[시작노드][끝노드]를 일차적으로 초기화 for i in range(5): d[i][i] = 0; for j in graph[i]: d[i][j[1]] = j[0]; # 점화식에 따라 중간에 다른거 거칠 때 기존 계산된 거리보다 작으면 업데이트 for a in range(5): for b in range(5): for k in range(5): d[a][b] = min(d[a][b], d[a][k] + d[k][b]); return d[1:]; print(floyd()); | cs |
3. 벨만포드 알고리즘
그래프의 음수 간선이 존재할 때 사용한다.
단순히 음수 간선이 존재할 때는 데이크스트라도 가능하지만, 음수 간선이 낀 사이클이 존재할 경우는 벨만포드 알고리즘으로 해결해야 한다.
기본적으로는 데이크스트라와 비슷하지만, 데이크스트라는 특정 노드(가장 거리가 짧은)에 연결된 간선들만 확인하지만, 벨만포드는 모든 간선에 대해 확인한다.
모든 간선에 대해 확인하면서 n-1번 확인하는데 이는 특정 노드에서 다른 노드까지 연결된 간선의 추가 최대 n-1개 일 수 있기 때문이다.
[1] --> [2] --> [3] --> [4] --> [5]
그리고 거리를 업데이트 하는 식은,
간선 시작점 최소 거리 + 간선 거리 가 지금까지 계산한 거리[간선 도착점 인덱스] 보다 작을 때,
지금까지 계산한 거리[간선 도착점 인덱스] = 간선 시작점 최소 거리 + 간선 거리 로 진행하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | INF = 1e9; graph = [ [], [(1,4),(2,2),(5,3)], [(2,4),(3,3)], [(3,2),(5,6)], [(3,3),(1,5)], [(1,3),(2,6)], [] ]; def bf(s) : d = [INF] * 7; # 시작지점 거리 초기화 및 방문 처리 d[s] = 0; # 시작지점에서의 거리 초기화 for i in graph[s]: d[i[1]] = i[0]; print(d); # 노드 갯수 - 1 만큼 반복 # 왜 노드 갯수 - 1 까지 반복하냐면.. 정점 A에서 B까지 거치는 간선의 가능한 최대 갯수가 노드 갯수 - 1 이기 때문. for n in range(7): # 모든 정점을 돌면서 기존 거리보다 새로 계산된 거리가 작아지면 업데이트 # 입력을 간선정보만 따로 보기좋게 안 받았으므로 그래프를 두번 돌면서 처리 for i in range(7): item = graph[i]; # i - 간선 시작지점 idx for j in item: idx = j[1]; dist = j[0]; # idx - 간선 끝지점 idx # 시작지점까지의 거리 + 현재 간선 거리 가 간선 끝지점의 거리보다 작을때 업데이트. if d[idx] > (d[i] + dist): print(f'cycle={n}') print(f'cycle={idx}') print(f'cycle={d[i] + dist}') d[idx] = d[i] + dist; print(d); if n == 6: print('음의 사이클 존재'); # print(d[1:]) return d[1:]; print(bf(4)); # 1회전 - [INF,6,2,0,1,3]; # ---> 4에서 바로 갈 수 있는 # 2 ~ 6 회전 - [5,2,0,1,3]; | cs |
덧글