글의 목적

알고리즘을 잊은 미래의 나를 이해시키기 위함

다익스트라 알고리즘

핵심: 시작 노드에서 모든 노드까지의 최단 경로를 계산한다.

사용이유: 원하는 시작 위치에서 다른 위치까지의 최단 경로를 계산하기 위해 사용한다.

사용예시: 그래프에서 a노드에서 z노드까지의 최단 경로 비용을 계산할 때

원리:
초기상태: 그래프를 준비하고 출발 노드(1번)를 설정하여 우선순위 큐에 삽입
(1) 우선순위 큐에서 원소를 꺼내면서 방문처리한다. 이미 방문된 노드라면 무시한다.
(2) 꺼낸 원소와 인접하면서 방문하지 않은 노드까지의 최단 경로를 계산하여 갱신한다.
(3) 갱신된 노드를 우선순위 큐에 삽입한다.
(4) 1~3번과정을 우선순위 큐가 빌 때까지 반복한다.

코드:

# 갱신된 노드는 우선순위큐(최소힙, 파이썬에서 최소힙은 heapq로 구현가능)에 넣는다.
# distance[]: 해당 노드까지의 최소값을 저장하는 리스트
def dijkstra(start):
  q=[]
  # 초기상태 설정: (거리, 노드)
  heapq.heappush(q, (0, start))
  # 최단거리테이블
  distance[start]=0
  while q:
     dist, now=heapq.heappop(q)
     # 갱신하여 우선순위 큐에 넣은 값이 이미 처리가 되었을 때 무시한다.
     # 이미 방문한 노드는 최단 거리 테이블에 최단 경로가 저장되어 있다.
     # 해당 if문의 의미: 이미 최소값으로 갱신되어 방문한 노드! 왜? 최소값으로 갱신 되었기 때문에 당연히 dist는 최소값을 담고 있는 distance[now]보다 작다.
     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]))

플로이드 워셜 알고리즘

핵심: 모든 노드에서 모든 노드까지의 최단 경로를 계산한다.(a노드부터 b노드까지의 최단경로, a노드부터 c노드까지의 최단경로.... 말그대로 각각의 노드가 나머지 노드까지 가는 최단 경로를 모조리 계산한는 것)

사용이유: 핵심과 동일

사용예시: 핵심과 동일

원리:
1. 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 즉, a에서 b로 가는 최단 거리와 a에서 k를 거쳐 b로 가는 거리를 비교한다.
2. 점화식: min(grahp[a][b], graph[a][k]+graph[k][b])

코드:

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])