Programming 기초/Python
[Python 자료구조 #가중치 그래프3] 최단 경로 알고리즘 - Dijkstra, Floyd
코딩상륙작전
2023. 5. 30. 23:09
* 최단 경로(shortest path)
- 최단 경로 문제는 가중치 그래프에서 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.
- 간선의 가중치를 시간으로 하면 "최단시간 경로", 거리로 하면 "최단거리 경로"가 된다.
- 인접 행렬에서 두 정점 사이의 간선이 없으면 None이 아니라 무한대 값(INF)을 저장한다.
- 간선의 가중치는 반드시 양수이다.
* Dijkstra의 최단 경로 알고리즘
- 하나의 시작 정점 v에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
- 만약 그래프의 모든 정점들 사이의 최단 경로를 구하려고 한다면 Dijkstra 알고리즘을 정점의 수만큼 반복하여 실행하면 된다.
- 하나의 정점에서 출발하여 모든 정점까지의 최단 경로를 찾는데 O(n^2)의 시간 복잡도를 갖는데, 모든 정점에서 출발한다면 알고리즘을 n번 반복해야 하므로 전체 복잡도가 O(n^3)이 된다.
- dist(v)는 정점 v의 dist값을 의미하고, w(A, B)는 간선 (A, B)의 가중치를 나타낸다.
- 집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합
- dist배열 : S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열. Prim의 MST 알고리즘에서와 유사. dist[v] = 0 (시작 정점)
- dist[] : 시작정점으로부터의 최단경로 거리를 저장
- found[] : 방문한 정점 표시를 위해 사용. 최초 모든 항목이 False
- path[] : 바로 이전 정점을 저장. 이전 정점을 따라 시작 정점까지 가는 경로가 최단 경로임.
INF = 9999
def choose_vertex(dist, found): # 최소 dist 정점을 찾는 함수
min = INF
minpos = -1
for i in range(len(dist)): # 모든 정점 중에서
if dist[i] < min and found[i] == False: # 방문하지 않은 최소 dist 정점
min = dist[i]
minpos = i
return minpos # 최소 dist 정점의 인덱스 반환def shortest_path_dijkstra(vtx, adj, start):
vsize = len(vtx) # 정점 수
dist = list(adj[start]) # dist 배열 생성 및 초기화
path = [start] * vsize # path 배열 생성 및 초기화
found = [False] * vsize # found 배열 생성 및 초기화
found[start] = True # 시작 정점 : 이미 찾아짐
dist[start] = 0 # 사작 정점의 거리 0
for i in range(vsize):
print("Step%2d: " % (i + 1), dist) # 단계별 dist[] 출력용
u = choose_vertex(dist, found) # 최소 dist 정점 u 탐색
found[u] = True # u는 이제 찾아짐
for w in range(vsize): # 모든 정점에 대해
if not found[w]: # 아직 찾아지지 않았으면
if dist[u] + adj[u][w] < dist[w]: # 갱신 조건 검사
dist[w] = dist[u] + adj[u][w] # dist 갱신
path[w] = u # 이전 정점 갱신
return path # 찾아진 최단 경로 반환vertex = ["A", "B", "C", "D", "E", "F", "G"]
weight = [
[0, 7, INF, INF, 3, 10, INF],
[7, 0, 4, 10, 2, 6, INF],
[INF, 4, 0, 2, INF, INF, INF],
[INF, 10, 2, 0, 11, 9, 4],
[3, 2, INF, 11, 0, INF, 5],
[10, 6, INF, 9, INF, 0, INF],
[INF, INF, INF, 4, 5, INF, 0],
]
print("Shortest Path By Dijkstra Algorithm")
start = 0
path = shortest_path_dijkstra(vertex, weight, start)
# A부터 모든 정점까지의 최단 경로 출력
for end in range(len(vertex)):
if end != start:
print("[최단경로: %s->%s] %s" % (vertex[start], vertex[end], vertex[end]), end="")
while path[end] != start:
print(" <- %s" % vertex[path[end]], end="")
end = path[end]
print(" <- %s" % vertex[path[end]])
------------------------------------------------------------------------------
# 각 단계별 dist[] 배열의 값 변화
Shortest Path By Dijkstra Algorithm
Step 1: [0, 7, 9999, 9999, 3, 10, 9999]
Step 2: [0, 5, 9999, 14, 3, 10, 8]
Step 3: [0, 5, 9, 14, 3, 10, 8]
Step 4: [0, 5, 9, 12, 3, 10, 8]
Step 5: [0, 5, 9, 11, 3, 10, 8]
Step 6: [0, 5, 9, 11, 3, 10, 8]
Step 7: [0, 5, 9, 11, 3, 10, 8]
[최단경로: A->B] B <- E <- A
[최단경로: A->C] C <- B <- E <- A
[최단경로: A->D] D <- C <- B <- E <- A
[최단경로: A->E] E <- A
[최단경로: A->F] F <- A
[최단경로: A->G] G <- E <- A
* Floyd의 최단 경로 알고리즘
- 그래프의 모든 정점사이의 최단경로를 한꺼번에 찾아준다.
- 3중 반복문을 사용하여 시간 복잡도가 O(n^3)이 된다.
- 매우 간결한 반복 구문을 사용한다는 특징이 있다.
- A^k[i][j]를 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로라고 하자.
INF = 9999
# 현재의 A행렬을 화면에 출력하는 함수
# A 행렬의 변화 과정을 보여주기 위해 알고리즘에 필요한 함수가 아닌 부가적으로 추가된 함수
def printA(A):
vsize = len(A)
print("====================================")
for i in range(vsize):
for j in range(vsize):
if A[i][j] == INF:
print(" INF ", end="")
else:
print("%4d " % A[i][j], end="")
print("")# Floyd의 최단경로탐색 함수.
def shortest_path_floyd(vertex, adj):
vsize = len(vertex) # 정점의 개수
A = list(adj) # 2차원 배열(리스트의 리스트)복사
# for i in range(vsize): # 파이썬 옛날 버전에서는 리스트 안의 리스트를 따로 복사해주는 과정이 필요했었다.
# A[i] = list(adj[i]) # 현재 버전에서는 아니다.
# 정점 k를 경유하는 것이 보다 좋은 경로이면 값을 변경하고
# 그렇지 않으면 이전 값을 유지한다.
for k in range(vsize): # 정점 k를 추가할 때
for i in range(vsize):
for j in range(vsize): # 모든 A[i][j] 갱신
if A[i][k] + A[k][j] < A[i][j]:
A[i][j] = A[i][k] + A[k][j]
printA(A) # 현재 A행렬 출력vertex = ["A", "B", "C", "D", "E", "F", "G"]
weight = [
[0, 7, INF, INF, 3, 10, INF],
[7, 0, 4, 10, 2, 6, INF],
[INF, 4, 0, 2, INF, INF, INF],
[INF, 10, 2, 0, 11, 9, 4],
[3, 2, INF, 11, 0, INF, 5],
[10, 6, INF, 9, INF, 0, INF],
[INF, INF, INF, 4, 5, INF, 0],
]
print("Shortest Path By Floyd Algorithm")
start = 0
path = shortest_path_floyd(vertex, weight)
-------------------------------------------------
Shortest Path By Floyd Algorithm
====================================
0 7 INF INF 3 10 INF
7 0 4 10 2 6 INF
INF 4 0 2 INF INF INF
INF 10 2 0 11 9 4
3 2 INF 11 0 13 5
10 6 INF 9 13 0 INF
INF INF INF 4 5 INF 0
====================================
0 7 11 17 3 10 INF
7 0 4 10 2 6 INF
11 4 0 2 6 10 INF
17 10 2 0 11 9 4
3 2 6 11 0 8 5
10 6 10 9 8 0 INF
INF INF INF 4 5 INF 0
====================================
0 7 11 13 3 10 INF
7 0 4 6 2 6 INF
11 4 0 2 6 10 INF
13 6 2 0 8 9 4
3 2 6 8 0 8 5
10 6 10 9 8 0 INF
INF INF INF 4 5 INF 0
====================================
0 7 11 13 3 10 17
7 0 4 6 2 6 10
11 4 0 2 6 10 6
13 6 2 0 8 9 4
3 2 6 8 0 8 5
10 6 10 9 8 0 13
17 10 6 4 5 13 0
====================================
0 5 9 11 3 10 8
5 0 4 6 2 6 7
9 4 0 2 6 10 6
11 6 2 0 8 9 4
3 2 6 8 0 8 5
10 6 10 9 8 0 13
8 7 6 4 5 13 0
====================================
0 5 9 11 3 10 8
5 0 4 6 2 6 7
9 4 0 2 6 10 6
11 6 2 0 8 9 4
3 2 6 8 0 8 5
10 6 10 9 8 0 13
8 7 6 4 5 13 0
====================================
0 5 9 11 3 10 8 # Dijkstra 알고리즘(시작정점0)의 결과와 동일
5 0 4 6 2 6 7 # 최종 A 행렬
9 4 0 2 6 10 6 # 최종 A 행렬
11 6 2 0 8 9 4 # 최종 A 행렬
3 2 6 8 0 8 5 # 최종 A 행렬
10 6 10 9 8 0 13 # 최종 A 행렬
8 7 6 4 5 13 0 # 최종 A 행렬
< 파이썬의 객체 복사 유의사항 >
1. A에 B라는 1차원 리스트를 복사할 때
A = B라고 하면 복사가 아닌 B 리스트 원본에 A가 함께 참조하게 된다.
A= list(B)라고 해야 한다. 이 코드는 생성자를 이용해 새로운 객체를 생성한 다음 변수 A가 이를 참조한다.
2. A에 2차원 배열 adj을 복사할 때A = adj 라고 하면 마찬가지로 A가 함께 참조한다.A = list(adj)라고 하면 새로운 리스트 객체는 생성되었지만, 리스트 안에 들어가는 리스트 객체들은 생성되지 않았다.for i in range(vsize): A[i] = list(adj[i])위 반복문구조를 덧붙이는 등, 각 행에 대한 리스트를 각각 생성하여 복사해야 2차원 배열을 온전히 복사한 것이 된다.(파이썬 버전 3.10.11 기준. 2차원 배열도 1차원 리스트 복사처럼 간단하게 list[adj]로 복사할 수 있다.)
3. copy 모듈을 사용하는 것.
copy 모듈의 deepcopy() 함수를 이용하면 2차원 배열도 쉽게 복사할 수 있다.
imort copy
A=copy.deepcopy(adj)