다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.
간선에 가중치가 없다면 너비 우선 탐색(BFS)으로도 충분히 풀 수 있지만, 간선에 가중치가 있다면 풀기가 매우
힘들어진다. 간선에 가중치가 있다면 다익스트라 알고리즘을 사용해서 풀도록 하자!!
다익스트라 알고리즘은 동작 과정은 아래와 같다.
1. 출발 노드 지정
2. 최단 거리 테이블 초기화
3. 방문한 적 없는 노드 중에서 최단 거리가 제일 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 거리를 구하여 최단 거리 테이블을 업데이트
5. 위 3, 4번 과정을 모든 노드를 방문할 때까지 반복
아래 코드는 파이썬으로 구현한 다익스트라 알고리즘 예시이다.
백준 1753번 최단경로)
import heapq
import sys
input = sys.stdin.readline
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
dis[start] = 0
while q:
d, now = heapq.heappop(q)
if dis[now] < d:
continue
for v, w in graph[now]:
cost = d + w
if cost < dis[v]:
dis[v] = cost
heapq.heappush(q, (cost, v))
V, E = map(int, input().split())
start = int(input())
INF = 10**9
dis = [INF]*(V+1)
graph = [[] for _ in range(V+1)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w))
dijkstra(start)
for n in dis[1:]:
print(n if n != INF else "INF")
백준 알고리즘 문제 풀이)
백준 알고리즘 1753번 최단경로(python)
기본적인 다익스트라 알고리즘 문제이다. import heapq import sys input = sys.stdin.readline def dijkstra(start): q = [] heapq.heappush(q, (0, start)) dis[start] = 0 while q: d, now = heapq.heappop(q)..
jinho-study.tistory.com
백준 알고리즘 1504번 특정한 최단 경로(python)
기본적인 다익스트라 문제이다. 다익스트라를 1(맨 처음 노드), v1, v2 기준으로 3번 돌려서 3개의 최단 거리 테이블을 생성하고 1 -> v1 -> v2 -> n 순서로 갈 때와 1 -> v2 -> v1 -> n 순서로 갈 때의 거리
jinho-study.tistory.com
백준 알고리즘 1446번 지름길(python)
다익스트라 문제이긴 한데 조금 더 쉽게 풀 수 있는 문제이다. BFS랑 매우 비슷한 풀이다. 1. 최단거리 테이블 생성 -> [i for i in range(D+1)] = [0, 1, 2, 3, ... , D] 2. 한 칸 전 위치의 테이블 값+1이 현..
jinho-study.tistory.com
백준 알고리즘 1916번 최소비용 구하기(python)
기본적인 다익스트라 문제이다. import heapq import sys INF = sys.maxsize input = sys.stdin.readline def dijkstra(start): q = [] heapq.heappush(q, (0, start)) dis[start] = 0 while q: d, now = heapq.he..
jinho-study.tistory.com
백준 알고리즘 5972번 택배 배송(python)
기본적인 다익스트라 문제이다. import heapq import sys INF = sys.maxsize def dijkstra(start): q = [] heapq.heappush(q, (0, start)) dis[start] = 0 while q: d, now = heapq.heappop(q) if dis[now] < d: c..
jinho-study.tistory.com
백준 알고리즘 14284번 간선 이어가기 2(python)
기본적인 다익스트라 문제이다. import heapq import sys INF = sys.maxsize # input = sys.stdin.readline def dijkstra(start): q = [] heapq.heappush(q, (0, start)) dis[start] = 0 while q: d, now = heapq...
jinho-study.tistory.com
백준 알고리즘 17396번 백도어(python)
기본적인 다익스트라 문제이긴 하다만, N-1번째 분기점을 제외하고 상대의 시야에 보이지 않는 분기점에만 방문해야 한다는 차이점이 있다. import heapq import sys INF = sys.maxsize input = sys.stdin.readli..
jinho-study.tistory.com
백준 알고리즘 1238번 파티(python)
골드 3 난이도 치고는 쉬운 다익스트라 알고리즘 문제이다. N-1개(1->X->1, 2->X->2, ..., N->X->X (X->X->X 제외))의 최단경로 중 최댓값을 출력해주면 된다. import heapq import sys INF = sys.maxsize # input..
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 플로이드-와샬(Floyd-Warshall) 알고리즘 (백준 문제 포함) (0) | 2021.03.22 |
|---|---|
| 우선순위 큐, 힙(Priority Queue, heap) (백준 문제 포함) (0) | 2021.03.22 |
| 퇴각검색(Backtracking) (백준 문제 포함) (0) | 2021.03.20 |
| 동적 계획법(Dynamic programming) (백준 문제 포함) (0) | 2021.03.17 |
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |