[알고리즘] 최단 경로 알고리즘 | 다익스트라 | 플로이드 워셜

 

 

~목차~

최단 경로 문제

다익스트라 알고리즘

플로이드워셜 알고리즘

---

 

최단 경로 문제

최단 경로 문제는 그래프 문제로 우테캠 6기 코딩테스트에도 나왔었다

최단 경로 알고리즘은 크게 두 가지로 다익스트라(Dijkstra, 데이크스트라) 알고리즘과 플로이드 워셜 알고리즘이 있다

 

기본적으로 그래프에 대한 이해를 바탕으로 알고리즘이 진행된다

노드에서 다른 노드로 접근 방법이 없다면 무한수(int(1e9) in Python)로 표시한다.

 

 

 

다익스트라 알고리즘

시작 노드로부터 각 노드까지 최단 경로를 구할 수 있는 알고리즘이다.

문제 해결을 위한 방법은 2가지가 있다. 리스트(배열)을 사용하거나 우선순위 큐 사용하는 것이다.

 

리스트를 사용하는 것이 우선순위 큐를 사용하는 것보다 쉽지만 시간 복잡도에서 차이가 많이 나므로

우선순위 큐를 사용하여 문제를 푸는 것에 익숙해지도록 하자!

 

 

1. 리스트(배열) 사용

O(V²) 의 시간 복잡도를 갖는다.(V : 노드 수)

 

해당 글에서는 우선순위 큐의 풀이 방법만을 다룬다

 

 

2. 우선순위 큐 사용

O(ElogV)의 시간 복잡도를 갖는다. ( E : 간선 수, V : 노드 수)

우선순위 큐를 사용하기 위해서 Python의 heapq 모듈을 사용함

 

1) 각 그래프의 인접 행렬이나 인접 리스트는 주어진 정보에 따라 생성한다.

2) 시작 노드로 부터 각 노드의 거리를 저장할 1차원 배열을 선언하고 무한수로 초기화 (2차원 배열로 확장되기도 함)

3) 우선순위 큐를 선언하여 시작 노드와 거리를 삽입한다.

3) 큐에 값이 있을 때까지 반복하며 거리가 최소가 되는 노드를 꺼낸다.

4) 우선순위 큐의 최소 노드가 방문된 적이 없다면(이미 저장된 거리 정보보다 현재 거리가 작다면) 거리 정보를 업데이트

 

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

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

for _ in range(m):
    v1, v2, d = map(int, input().split())
    graph[v1].append((v2, d))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # 우선순위 큐, q에 (거리, 시작 노드) 삽입
    distance[start] = 0
    while q:
        dist, now = q.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])
        
        
# 입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
# 출력 예시
0
2
3
1
2
4

 

 

 

문제 풀이 모음

2023.05.16 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 1753 최단 경로 | 다익스트라 알고리즘

2023.05.16 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 18352 특정 거리의 도시 찾기 | 다익스트라 알고리즘

2023.05.16 - [📁문제 풀이/🧩Programmers] - [Python] 프로그래머스 가장 먼 노드 | BFS | 다익스트라

 

 

 

 

플로이드 워셜 알고리즘

다익스트라와 비교하여 점화식 하나만 기억하고 있다면 쉽게 구현할 수 있다.

또한 다른 점은 시작 노드 뿐만 아니라 각 노드에서 다른 노드까지 최단 경로를 모두 알 수 있다.

 

문제 해결을 위한 포인트는 a -> b 경로와 a -> k -> b 경로 중 더 작은 값 업데이트를 반복하여 노드 별 가장 작은 거리를 찾는다

2차원 배열로 각 노드 거리를 표시한다

 

k를 구하기 위해 N회, a를 구하기 위해 N회, b를 구하기 위해 N회를 수행하므로 3중 for문이 작성되고

시간복잡도는 O(N³)가 된다

 

플로이드 워셜 알고리즘에서 기억할 점화식은

D_ab = min( D_ab ,  D_ak + D_kb)

 

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()
    
    
# 입력 예시
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
# 출력 예시
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0

 

 

 

플로이드 워셜 문제 풀이 모음

2023.05.16 - [📁문제 풀이/🧩Baekjoon] - [Python] 백준 11404 플로이드 | 플로이드 워셜

 

 

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

💡 궁금한 점이 있다면 댓글 달아주세요!