최단 경로 문제는 가중치 그래프에서 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.
간선의 가중치를 시간으로 하면 "최단시간 경로", 거리로 하면 "최단거리 경로"가 된다.
인접 행렬에서 두 정점 사이의 간선이 없으면 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까지의 최단 경로라고 하자.
"Floyd 알고리즘" 출처 : 파이썬으로 쉽게 풀어쓴 자료구조
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행렬 출력
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)
