최단 경로

"가장 짧은 경로를 찾는 알고리즘" - 길찾기 문제

 

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

- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

- '음의 간선' 즉, 0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작한다.

- 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다.

 

[알고리즘 원리]

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

5. 위 과정에서 3번과 4번을 반복

 

- 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 갱신

- 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인

- '방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인'해 그 노드에 대하여 4번 과정을 수행

 

[구현하는 방법]

1. 구현하기 쉽지만 느리게 동작하는 코드

2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

 

 

Step 0. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드(1)에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택된다.

노드번호	1	2	3	4	5	6
거리	0	int(1e9)	int(1e9)	int(1e9)	int(1e9)	int(1e9)

Step 1. 1번 노드를 거쳐 다른 노드로 가는 비용계산.

 - 1번 노드를 거쳐서 2번, 3번, 4번 노드로 가는 최소 비용은 각각 2(0+2), 5(2+3), 1(0+1)이다.

노드번호	1	2	3	4	5	6
거리	0	2	5	1	int(1e9)	int(1e9)

Step 2. 이후의 모든 단계에서도 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 따라서 4번 노드가 선택된다. 

- 4번 노드를 거쳐서 3번과 5번 노드로 가는 최소 비용은 차례대로 4(1+3), 2(1+1)이다.

- 이 두값은 기존의 리스트에 담겨 있던 값보다 작으므로 다음 처럼 리스트를 갱신한다.

노드번호	1	2	3	4	5	6
거리	0	2	4	1	2	int(1e9)

Step 3. 2번과 5번 노드까지의 최단 거리가 2로 값이 같은데, 일반적으로 번호가 작은 노드를 선택한다. 2번 노드를 거쳐서 가는 경우, 현재의 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.

ex. 2번 노드를 거쳐서 3번 노드로 이동하는 경우, 5(2+3)만큼의 비용이 발생함.

노드번호	1	2	3	4	5	6
거리	0	2	4	1	2	int(1e9)

Step 3. 5번 노드 선택. 3번 노드로 가는 최단 더리 1+1+1 = 3(1->4->3)으로 갱신

노드번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

(반복)

 

최종 최단 거리 테이블

노드번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

- 1번 노드에서 출발 했을 때의 최단 경로이다.

- 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다.

 

알고리즘 구현

방법 1. 간단한 다익스트라 알고리즘

시간복잡도 : O(V**2) V:노드 개수

- 처음에 각 노드에 대한 최단거리를 담는 1차원 리스트 선언

- 이후에 단계마다 '방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트이 모든 원소를 확인(순차 탐색)

 

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())
    # a번 노드에서 b번 노드로 가는 비용이 c
    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]
    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n-1):
        now = get_smallest_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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

방법 2. 개선된 다익스트라 알고리즘

최악의 경우에도 O(ElogV) 보장 V:노드의 개수, E:간선의 개수

- 최단 거리가 가장 짧은 노드를 선형적으로 찾는것이 아닌 더 빠르게 찾는 방법으로 !! - 힙 자료구조 사용

 

힙 설명

우선 순위 큐 - '우선순위가 가장 높은 데이터를 가장 먼저 삭제'

자료 구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

최소 힙 - '값이 낮은 데이터가 먼저 삭제'

최대 힙 - '값이 큰 데이터가 먼저 삭제'

 

"현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용"

 

Step 0. (1번 노드가 출발 노드인 경우를 고려)

(거리 : 0, 노드 : 1)의 튜플로 표현 - heapq 라이브러리는 원소로 튜플을 입력받으면 튜플의 첫 번째 원소를 기준으로 우선 순위 큐를 구성한다.

노드 번호	1	2	3	4	5	6
거리	0	int(1e9)	int(1e9)	int(1e9)	int(1e9)	int(1e9)

(거리: 0, 노드: 1)

 

Step 1.

우선순위 큐를 이용하고 있으므로 거리가 가장 짧은 노드를 선택하기 위해서는 우선순위 큐에서 그냥 노드를 꺼내면 된다. (거리가 짧은 원소가 우선순위 큐의 최상위 원소로 위치해 있음) 따라서, 우선순위 큐에서 노들르 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시하면 되고, 아직 처리하지 않은 노드에 대해서만 처리

노드 번호	1	2	3	4	5	6
거리	0	2(0+2)	5(2+3)	1(0+1)	int(1e9)	int(1e9)

(거리: 1, 노드:4) (거리: 2, 노드: 2) (거리: 5, 노드: 3)

 

Step 2.

노드번호	1	2	3	4	5	6
거리	0	2	4(1+3)	1	2	int(1e9)

(거리: 2, 노드: 2) (거리: 2, 노드: 5) (거리: 4, 노드: 3) (거리: 5, 노드: 3)

 

Step 3. 

노드번호	1	2	3	4	5	6
거리	0	2	4	1	2	int(1e9)

(거리: 2, 노드: 5) (거리: 4, 노드: 3) (거리: 5, 노드: 3) => 갱신할 거리 없음

 

Step 4. 

노드번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

(거리: 3, 노드: 3) (거리: 4, 노드: 3) (거리: 4, 노드: 6) (거리: 5, 노드: 3)

 

(반복)

 

Step 8. 최종 테이블

노드번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

- 앞의 코드와 비교 했을때 get_smallest_node()라는 함수 작성이 필요 없다.

- '최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체 가능하다.

 

import heapq
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 = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    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]))

dijkstra(start)

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

 

플로이드 워셔 알고리즘

"모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"

- 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교해서 더 작은 값으로 갱신

- 3중 반복문을 이용하여 이 점화식에 따라 최단 거리 테이블을 갱신

Step 0.

출발/도착	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	INF
3번	5	INF	0	4
4번	INF	INF	2	0

 

Step 1. 단순히 1번 노드를 거쳐 가는 경우를 고려 6 = 3P2가지 경우에 대해서만 고민

출발/도착	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

 

Step 2. 2번 노드를 거쳐 가는 경우

(1, 3) (1, 4) (3, 1) (3, 4) (4, 1) (4, 3)

출발/도착	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

 

Step 3. 3번 노드를 거쳐 가는 경우

(1, 2) (1, 4) (2, 1) (2, 4) (4, 1) (4, 2)

출발/도착	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

Step 4. 4번 노드를 거쳐 가는 경우

출발/도착	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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()

 

---

미래 도시

공중 미래 도시에는 1번부터 N번까지의 회사가 있는데, 특정 회사끼리는 서로 도로를 통해 연결(양방향 이동 가능)되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 팔고자 한다.

판매원 A는 1번 회사에서 출발하여 K번 회사에 방문한 뒤 X번 회사로 가는 것이 목표다. 이때 최소 이동 시간을 구하시오.( 도달 할 수 없다면 -1 출력)

 

INF = int(1e9)
# 노드의 개수 및 간선의 개수 입력
n,m = map(int, input().split())
# 2차원 리스트(그래프, 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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 = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
# 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력 받기
x, k = map(int, input().split())

# 점화식에 따라 플로이드 워셜 알고리즘 수행
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])
# 수행된 결과 출력
distance = graph[1][k] + graph[k][x]

# 도달할 수 없는 경우, -1 을 출력
if distance >= INF:
    print("-1")
else:
    print(distance)

 

전보

어떤 나라에는 N개의 도시가 있다. X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야한다. 어느날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메세지를 보내고자 한다. 메세지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 떄, 도시 C에서 보낸 메세지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

Tip. 한 도시에서 다른 도시까지의 최단 거리문제로 치환 -> 다익스트라 알고리즘 이용(우선순위 큐 이용)

 

import heapq
import sys

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

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

for _ in range(m):
    x,y,z = map(int, input().split())
    graph[x].append((y,z))

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

dijkstra(start)

count = 0
max_distance = 0
for d in distance:
    if d!=INF:
        count += 1
        max_distance = max(max_distance,d)
        
print(count-1, max_distance)