[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 09 최단 경로 - 이론 및 예제

가장 빠른 길 찾기

 

1 _ 가장 빠르게 도달하는 방법

• 최단 경로 (Shortest Path) 알고리즘: 가장 짧은 경로를 찾는 알고리즘
• 최단 거리 알고리즘 유형
  • 대표 유형: 다익스트라 최단 경로 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘
  • 코딩 테스트에 많이 등장하는 유형: 다익스트라 최단 경로 알고리즘, 플로이드 워셜 알고리즘
• 최단 경로 문제 표현 방법
  • 보통 그래프응 이용해 표현
  • 각 지점은 '노드', 지점을 연결하는 도로는 '간선'

 

---

 

2 _ 다익스트라 최단 경로 알고리즘

• 다익스트라(Dijkstra) 최단 경로 알고리즘
  • 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
  • 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
• 다익스트라 알고리즘 특징
  • 음의 간선이 없을 때 정상적으로 동작
  • '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신
• 다익스트라 알고리즘
  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다.
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  5. 위 과정에서 3번과 4번을 반복한다.
• 다익스트라 알고리즘 구현 방법
  1. 구현하기 쉽지만 느리게 동작하는 코드
  2. 구현하기에는 조금 더 까다롭지만 빠르게 동작하는 코드

 

---

 

3 _ 다익스트라 알고리즘 소스코드

• 간단한 다익스트라 알고리즘

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))


def get_smallest_node():
    min_value = INF
    index = 0

    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i

    return index


def dijkstra(start):
    distance[start] = 0
    visited[start] = True

    for j in graph[start]:
        distance[j[0]] = j[1]

    for i in range(n-1):
        now = get_smmallest_node()
        visited[now] = True

        for j in graph[now]:
            cost = distance[now] + j[1]

            if cost < distance[j[0]]:
                distance[j[0]] = cost    


dijkstra(start)


for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

• 개선된 다익스트라 알고리즘

import headq
import sys
input = sys.stdin.readline
INF = int(1e9)


n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))


def dijkstra(start):
    q = []
    headq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = headq.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
                    headq.heappush(q, (cost, i[0]))


dijkstra(start)


fot i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

---

 

4 _ 플로이드 워셜 알고리즘

• 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)
  • 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• 예시

1. 초기 테이블
   

   

2. step 0
   

   

3. step1
   

   

4. step2

5. step3

6. step4

7. 최종 결과

 

---

 

5 _ 플로이드 워셜 알로리즘 소스코드

INF = int(1e9)


n = int(input())
m = int(input())


graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1):
	for b in range(1, n+1):
    	if a == b:
        	graph[a][b] = 0
            
            
for _ in range(m):
	a, b, c = map(int, input().split())
    graph[a][b] = c
    
    
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])
            
            
for a in range(1, n+1):
	for b in range(1, n+1):
    	if graph[a][b] == INF:
        	print("INFINITY", end=" ")
        else:
        	print(graph[a][b], end=" ")
    print()

 

---

 

위 내용은 저자 나동빈의 < 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 을 읽고, 공부한 내용입니다.

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬