최단 경로 알고리즘 (다익스트라 알고리즘, 플로이드 워셜 알고리즘)

  말 그대로 최단 경로를 찾는 알고리즘이다. 길 찾기 문제라고도 불린다 한다. 노드와 간선으로 이루어진 그래프 상황에서 유용하다. 정의는 어려운 것 없으니 바로 본론으로 들어가 보겠다.

 

 다익스트라 알고리즘 (Dijkstra Algorithm)

 다익스트라 알고리즘은 출발 노드를 정하여 시작해서 다른 특정 지점까지의 최단 경로를 찾는 알고리즘이다. 출발 기준 갈 수 있는 노드의 거리를 1차원 리스트에 저장한다. 처음에 리스트의 모든 값은 무한대(INF = int(1e9)로 선언)로 값을 할당한다. 끝났을 때 값이 INF인 인덱스는 시작 노드에서 갈 수 있는 방법이 없는 것이다.

 

 시작 노드 번호의 인덱스는 처음에 0 으로 바꾸고 진행한다. 기본적인 개념은 시작 노드에서 갈 수 있는 노드의 거리를 리스트에 최신화시킨 후 시작 노드를 방문했다고 체크한다. 그다음 거리가 가장 짧은 노드를 골라 갈 수 있는 노드를 다시 찾아 리스트를 최신화하고 이 노드도 방문했다고 체크한다. 이때 거리가 INF가 아니라면 현재 거리 값과 지금 노드를 거쳤을 때 거리를 계산하여 짧은 것을 거리로 정한다. 모든 노드가 방문했다고 체크될 때까지 반복한다. (방문했다고 체크한다 했을 때 노드는 밑줄 친 거리가 가장 짧아서 선택된 노드를 의미한다. 최신화한 노드를 체크하는 것이 아니다.)

 

1. 거리를 표시하는 리스트를 dist, 방문을 체크하는 bool형 리스트를 check라 정하고 모두 false를 선언한다.

2. 시작 노드가 1이라고 주어졌다 가정한다. dist[1]을 0으로 바꾸고 나머지 dist [2], dist [3], dist [4],,,는 INF로 값을 정한다.

3. 노드 1에서 갈 수 있는 노드들의 dist를 최신화 한다. 예를 들면 dist[2] = 4, dist[4] = 1 그 후 check[1]을 true로 바꾼다.

4. dist가 가장 짧고 check가 false인(방문하지 않은) 노드를 찾는다.

5. 3의 방법을 check가 모두 true일 때 까지 반복한다.

 

 기본 개념은 이러한데 dist가 가장 짧은 노드를 찾을 때 매번 선형 검색을 해주어야 한다. 시간을 더 줄이기 위해 heap(우선순위 큐이므로 거리가 작으면 우선순위가 높다. (우선순위로 사용할 값, 데이터)의 형태로 저장한다.)을 이용한다. 방법은 같은데 위의 4번 방법을 heap이 알아서 해주는 것이다.

def dijkstra(start):
	q=[]
	heapq.heappush(q,(0,start))
	distance[start] = 0
	while q:
		dist, now = heapq.heappop(q)
		if distance[now] <dist:
			continue
		for i in graph[now]:
			cost = dist + i[1]
			if cost < distance[i[0]]:
				distance[i[0]] = cost
				heapq.heappush(q, (cost, i[0]))

 if distance[now] < dist: continue 부분은 현재 노드가 이미 처리된 적이 있으면 continue로 넘어가는 것인데 뭔가 와닿지 않아서 직접 예제를 그려보면서 해봤는데 그냥 따라 하면 된다. ㅋㅋㅋ 간단히 설명하자면 heappop을 해서 꺼낸 값은 지금 연산이 일어나기 전에 넣어둔 것이다. 지금 값 (distance[now])보다 heap에서 꺼낸 값이(dist) 크다면 heap에 넣은 이후 꺼내기 전까지 그 사이에 다른 더 빠른 길을 찾은 것이기에 이 값은 쓸모가 없다. 그래서 continue로 넘어가는 것이다. (또 의문 품고 다시 삽질하지 마 맞으니까 그냥 해 미래의 태호야.) 

 

 모든 연산이 끝나면 dist(거리를 저장하던 리스트)에 시작 노드에서 가는 최단 거리가 저장되어있다.

 

 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

 플로이드 워셜 알고리즘은 특정 시작 점에서 출발하는 최단 경로가 아닌 모든 노드에서 다른 모든 지점까지의 최단 경로를 구한다. 즉 존재하는 노드들 사이의 모든 최단 경로를 구하는 것이다. 2차원 리스트를 통해 그래프를 저장한다. graph[1][3]은 1번 노드에서 3번 노드로 가는 거리가 저장되어 있다. 점화식을 사용하여 다이나믹 프로그래밍으로도 볼 수 있다.(전에 구해놨던 거리를 사용하기 때문이다.) 2차원 리스트에 거리를 저장하며 자기 자신에 출발하여 자기 자신에 도착하는(graph[1][1] 같은) 곳은 0, 길이 없는 곳은 INF를 저장한다. 

 

 1. 주어진 경로를 (경유해가지 않고 바로 이어진 즉 처음 문제에 주어진 간선들을 이용해서) 2차원 리스트에 저장한다.

 2. 경유해 가는 케이스를 구해 지금 리스트의 값보다 작으면 값을 바꾼다.

for k in range(1, n+1):
	for a in range(1, n+1):
		for b in range(1, n+1):
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

 경유하는 곳의 노드를 k로 정한 것이다. 연결 안 되어 있는 곳은 INF이기에 min에서 걸러진다. k가 a나 b와 같은 경우도

ex) k=2, a=2, b=3 => graph[2][3] = min(graph[2][3], graph[2][2] + graph [2][3]) 어차피 graph[2][2]는 0 이기 때문에 알아서 처리된다. 이 역시 꼬투리 잡아서 케이스 만들어 직접 손으로 그려보았는데 맞게 동작한다.