최단경로 알고리즘 기초개념 및 구현실습
.
그림, 실습코드 등 학습자료 출처 :
1) https://github.com/ythwork
2) https://hsp1116.tistory.com/45
1. 최단경로의 사전조건
1) 음수 사이클이 없다.
2) 방향그래프다.(directed graph)
3) 가중치그래프다.(weighted graph)
4) 경로의 길이 : 에지 가중치의 합
2. 음수싸이클이란
- 노드 간 이동하는 에너지가 음수가 되면 안된다.
음수싸이클을 비유를 들면 기름을 가득 채워서 서울 -> 부산 -> 광주 -> 서울을 오니까 기름이 가득 채워져 있는 것과 바슷하다.
- 다익스트라는 음수가중치를 인정하지 않고, 벨만포드 알고리즘은 음수가중치(음수에지)를 인정한다. 그리고 이 둘 다 음수사이클은 인정하지 않는다. 결론적으로 음수던 양수던 사이클을 인정하지 않는다.
예를 들어서 아래 그림과 같다.
3. 최단 경로 알고리즘의 종류
1) 하나의 출발점과 나머지 모든 목적지
- 다익스트라 알고리즘
탐욕 알고리즘 기반
음수 가중치가 없다.
- 벨만-포드 알고리즘
2) 모든 (출발점, 목적지) 쌍
플로이드-워셜 알고리즘(다이나믹 프로그래밍)
4. 다익스트라 알고리즘
1) 탐욕 알고리즘 기반
2) 음수가중치가 없다.
3) 최단 경로가 발견된 정점의 집합 S
4) 정점 v의 distance[v]
출발 정점에서 S에 있는 정점만 거쳐 v에 도달하는 경로의 길이
각 노드마다 distance라는 배열이 있고, predecessor가 있는데 프림알고리즘의 from과 역할이 비슷하다.
5. relaxation of an edge
6. Graph representation
Adjacency matrix
다익스트라에서 shortest path를 인접행렬로 표현하였다.
예를들어 아래그림에서 0번 터택스와 1번 버택스가 있으면 그둘의 에지가중치를 해당 행렬에 입력한다.
7. 다익스트라 알고리즘
-
알고리즘 예시로 아래 그림에서 0번 노드에서 3번 노드로 가는 최단경로를 구해보자.
-
용어설명
1) D : distance(소스부터 시작해서 s에 있는 정점들만 거쳐서 도달하는 거리)
2) P : 전임자(최단거리 중에서 나 이전에 오는 노드)
- 경로탐색과정
step1) 시작정점을 입력하면 (예를 들어 0을 입력하면)
0 -> 0을 가는 에지 가중치를 구한다. 에지 가중치는 0 이놈이 시작 정점의 가중치
step2) 주변에 relax 를 구해야 한다
(0->1) : 0 + 10
(0->2) : 0 + 3
step3) 2가 더 작으므로 2을 S에 업데이트 해준다.
step2) ~ step3)을 반복한다.
- print_shortest_path
shortestPath 클래스에는 distance 배열과 p 배열이 정의되어 있다.
print_shortest_path 함수에서 0 -> 2 -> 3번으로 제대로 출력을하려면 재귀함수를 이용해야 한다.
if sp.source==dest:
print("{}".format(dest), end=" ")
return
이 코드가 기저조건이다.
Graph.print_shortest_path(sp, sp.p[dest])
그리고 이 코드가 재귀적으로 돌게 될 것이다.
- 파이썬 코드구현 예시
class ShortestPath:
def __init__(self, s, distance, p):
self.source=s
self.distance=distance
self.p=p
class Graph:
#모든 가중치보다 충분히 큰 수
BIG_NUMBER=2000
@staticmethod
def print_shortest_path(sp, dest):
if sp.source==dest:
print("{}".format(dest), end=" ")
return
if sp.p[dest]!=None:
Graph.print_shortest_path(sp, sp.p[dest])
else:
print("There is no path")
return
print("{}".format(dest), end=" ")
def __init__(self, vnum):
self.adjacency_matrix=[[None for _ in range(vnum)] for _ in range(vnum)]
self.vertex_num=vnum
def insert_edge(self, u, v, w):
self.adjacency_matrix[u][v]=w
def find_min(self, distance, S):
_min=self.BIG_NUMBER
min_v=-1
for i in range(self.vertex_num):
if i not in S and distance[i] < _min:
_min=distance[i]
min_v=i
return min_v
def dijkstra(self, s):
#출발 정점에서 S에 있는 정점만 거쳐 v에 도달하는 경로의 길이
distance=[self.BIG_NUMBER for _ in range(self.vertex_num)]
#predecessor
#distance[v]를 구할 때 경로 상에서 v의 바로 이전 노드
p=[None for _ in range(self.vertex_num)]
#최단 경로가 발견된 정점의 집합
S=set()
distance[s]=0
while len(S) < self.vertex_num:
#S에 속하지 않으면서 distance가 가장 작은 정점 v
v=self.find_min(distance, S)
#S=S U {v}
S.add(v)
for u in range(self.vertex_num):
w=self.adjacency_matrix[v][u]
#w가 None이 아니면 u가 v에 adjacent
#relaxation
#if distance[u] > distance[v]+w
#then distance[u] = distance[v]+w
if w!=None and u not in S and distance[u] > distance[v]+w:
distance[u] = distance[v]+w
p[u]=v
sp=ShortestPath(s, distance, p)
return sp
if __name__=="__main__":
g=Graph(4)
g.insert_edge(0, 1, 10)
g.insert_edge(0, 2, 3)
g.insert_edge(1, 3, 5)
g.insert_edge(2, 1, 5)
g.insert_edge(2, 3, 8)
g.insert_edge(3, 1, 4)
g.insert_edge(3, 2, 12)
source=0
sp=g.dijkstra(source)
for i in range(g.vertex_num):
print('distance[{0}] : {1}, p[{0}] : {2}'.format(i, sp.distance[i], sp.p[i]))
dest=3
print("path from {} to {}".format(source, dest))
g.print_shortest_path(sp, dest)
print()
distance[0] : 0, p[0] : None
distance[1] : 8, p[1] : 2
distance[2] : 3, p[2] : 0
distance[3] : 11, p[3] : 2
path from 0 to 3
0 2 3
8. 플로이드-워쉘 알고리즘
-
다익스트라는 single source shortest path problem인 반면에 플로이드-워쉘은 모든 (출발점, 목적지) 쌍에 대한 최단경로를 구한다.
-
또한 다익스트라 알고리즘은 음수가중치를 인정하지 않지만 플로이드-워쉘은 음수 에지를 인정한다.
-
모든 정점에 대한 경로를 계산하므로 거리를 저장할 2차원 테이블이 필요하다.
-
플로이드-워쉘 알고리즘은 다이나믹 프로그래밍으로 부터 나온 개념이고, 다이나믹 프로그래밍은 optimal substructure의 개념을 이용하여 최단경로를 찾는다는 말이다. 다시말해 재귀함수가 필요하다. optimal substructure는 특정경로 안에 무수히 많은 경로가 있을때, 중간정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 것이다.
-
플로이드-워쉘 알고리즘은 두개의 테이블을 사용한다.
하나는 모든경로에 대한 비용을 저장하는 테이블
다른 하나는 각 정점까지 가기 직전의 정점을 저장한 테이블이다.
이 각각의 테이블에는 최초에는 인접리스트에 대한 내용만 들어가게 되는데 구후 경로를 추가할때마다 두 테이블이 갱신되는 방식이다.
-
플로이드-워쉘 알고리즘은 재귀와 기저조건이 필요하다 !
-
A[i][j]는 i에서 j까지 가는 최단경로길이
-
w(i,j) 는 i와 j의 에지가중치
-
A의 k승[i][j] 의미 : 0번 버텍스에서 시작해서 k번 버텍스까지 경유가 가능한 정점, 0에서 k를 거쳐도 되고 안거쳐도 되지만 경유가 가능하다는 의미
ex)
A의 -1승[0][3] = 0번인덱스부터 3번까지 가야하는데 -1번 인덱스를 거쳐갈 수 있다. -1번만 거쳐서 3번까지 갈수 없다. 무한대
A의 0승[0][3] = 0번인덱스부터 3번까지 가야하는데 0번 인덱스를 거쳐갈 수 있다. 0번만 거쳐서 3번까지 갈수 없다. 무한대
A의 1승[0][3] = 0번인덱스부터 3번까지 가야하는데 1번 인덱스를 거쳐갈 수 있다. 30
A의 2승[0][3] = 0번인덱스부터 3번까지 가야하는데 2번 인덱스를 거쳐갈 수 있다. 5
-
path mat는 노드들간 거쳐간 버텍스 중에 가장 큰수를 저장해 놓는다.
-
플로이드-워쉘 알고리즘 설명
- 2차원 테이블을 하나만 쓰면 안되는 이유
- 플로이드-워쉘 알고리즘 예시
정점2에서 정점3까지의 최단거리를 구하는 예시
- 파이썬 코드구현 예시
from copy import deepcopy
class ShortestPath:
def __init__(self, A, path):
#2차원 배열 A
self.A=A
#2차원 배열 path
self.path=path
class Graph:
#모든 가중치보다 충분히 큰 수(inf 대신 사용)
BIG_NUMBER=2000
@staticmethod
def print_shortest_path(sp, source, dest):
#경로 중 source와 dest를 제외하고 출력한다
if sp.path[source][dest]==None:
return
# i~k까지 출력
Graph.print_shortest_path(sp, source, sp.path[source][dest])
# k 출력
print(sp.path[source][dest], end=" ")
# k~j까지 출력
Graph.print_shortest_path(sp, sp.path[source][dest], dest)
def __init__(self, vnum):
#A^-1 mat을 만들 때 if <u, v> not in E(G) then inf
#inf 대신에 모든 가중치보다 충분히 큰 수를 사용
self.adjacency_matrix=[[self.BIG_NUMBER for _ in range(vnum)] for _ in range(vnum)]
for i in range(vnum):
self.adjacency_matrix[i][i]=0
self.vertex_num=vnum
def insert_edge(self, u, v, w):
self.adjacency_matrix[u][v]=w
def floyd_warshall(self):
#A^-1 mat
A=deepcopy(self.adjacency_matrix)
#경로 기록을 위한 2차원 배열
path=[[None for _ in range(self.vertex_num)] for _ in range(self.vertex_num)]
for k in range(self.vertex_num):
for i in range(self.vertex_num):
for j in range(self.vertex_num):
#A^k[i][j]=min{A^(k-1)[i][j], A^(k-1)[i][k]+A^(k-1)[k][j]}
if A[i][j] > A[i][k] + A[k][j]:
A[i][j]=A[i][k]+A[k][j]
path[i][j]=k
sp=ShortestPath(A, path)
return sp
if __name__=="__main__":
# simple example
# g=Graph(4)
# g.insert_edge(0, 1, 12)
# g.insert_edge(0, 2, 3)
# g.insert_edge(1, 3, 15)
# g.insert_edge(1, 2, 5)
# g.insert_edge(2, 0, 7)
# g.insert_edge(2, 1, 6)
# g.insert_edge(2, 3, 2)
# g.insert_edge(3, 1, 13)
# g.insert_edge(3, 2, 6)
# source=0
# dest=3
# complicated example
g=Graph(6)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 2, 7)
g.insert_edge(0, 5, 9)
g.insert_edge(1, 3, 4)
g.insert_edge(1, 5, 2)
g.insert_edge(2, 0, 8)
g.insert_edge(2, 4, 6)
g.insert_edge(3, 0, 6)
g.insert_edge(3, 4, 2)
g.insert_edge(3, 5, 3)
g.insert_edge(4, 0, 8)
g.insert_edge(4, 2, 3)
g.insert_edge(4, 5, 10)
g.insert_edge(5, 1, 7)
g.insert_edge(5, 2, 4)
source=2
dest=3
sp=g.floyd_warshall()
print("A mat")
for i in range(g.vertex_num):
for j in range(g.vertex_num):
print("{}".format(sp.A[i][j]).rjust(4), end="")
print()
print()
print("path mat")
for i in range(g.vertex_num):
for j in range(g.vertex_num):
if sp.path[i][j]==None:
print("{} ".format("N").rjust(4), end="")
else:
print("{} ".format(sp.path[i][j]).rjust(4), end="")
print()
print()
print("path from {} to {}".format(source, dest))
print("{}".format(source), end=" ")
g.print_shortest_path(sp, source, dest)
print("{}".format(dest), end=" ")
A mat
0 5 7 9 11 7
10 0 6 4 6 2
8 13 0 17 6 15
6 10 5 0 2 3
8 13 3 17 0 10
12 7 4 11 10 0
path mat
N N N 1 3 1
3 N 5 N 3 N
N 0 N 1 N 1
N 5 4 N N N
N 0 N 1 N N
2 N N 1 2 N
path from 2 to 3
2 0 1 3