2022-07-23
처음에는 최단경로에 대한 알고리즘을 공부할 때 BFS만이 있던 나에게 점차적으로 최단경로 알고리즘은 다양하게 알려주었던 다익스트라 알고리즘,,,물론 이 말고도 다양한 상황에 따라서 각각의 좋은 최단경로 알고리즘이 있음은,,곧 다른 포스팅에서 정리해보겠다
🚩다익스트라 알고리즘
다익스트라 알고리즘의 상황적인 포인트를 간단하게 표현한다면
출발노드가 주어지고,다른 노드까지의 경로에 대한 최단경로를 구하라 할때!
그럼 여기까지만 보면 분명 이런 생각이 들 것이다?
"뭐야 그냥 bfs로 하면 되는거 아니야?"
맞다 하지만 다익스트라의 상황은 조금 다른건 기본 각 노드간의 즉 간선의 비용이 문제에서 주어질 때라는 것 이다.
bfs는 기본적으로 각 노드간의 비용이 1인상황일 때 이 차이점이 존재한다
따라서 문제에서 노드간의 간선에서의 비용정보가 드러나게 되고 출발노드가 설정되어 있다면??(단, 간선의 비용이 양일 때.. 음이게 되면,,벨만포드알고리즘으로 넘어가게된다,,)
다익스트라..!!
🔑다익스트라 알고리즘 구현
다익스트라 알고리즘을 구현할 때에 있어서 사실 상단히 코드가 긴게 사실이다
따라서 구현에 앞서 기본원리를 담아보자면
매번 가장 거리가 짧은 노드를 선택해서 임의의 횟수의 과정을 계속적으로 반복
그리디알고리즘의 일부분이라고 볼 수 있다
즉,매번 방문하지 않은 노드들 중에서 최단거리가 가장 짧은 노드를 선택하여 이동하게 된다
(근데 이 때 방문하지 노드에서 인접한 노드를 볼때 거리가 짧은 것을 선택하고 진행한다는 점에서 그리디하다고 볼 수 있는 것)
구현에 있어서 생각할 🔑키워드
1.노드와 간선간의 정보를 담아줄 인접리스트
graph=[[] for k in range(n+1)]2.각 노드까지의 최단경로정보를 담아줄 distance테이블
INF=int(1e9)
#여기서 1e9는 10억을 의미해서 무한대를 대신해서 그냥 그만큼 큰숫자를 넣은거로 생각하면 됨
distance=[INF]*(n+1)3.방문처리 정보를 담아줄 visited테이블
visited=[False]*(n+1)
#여기서 계속 n+1로 리스트의 크기를 맞춰주는 이유는 노드정보를 1번부터 시작할려고
#0번은 그냥 안쓰는게 맞추기 쉬워서 그렇다4.(제일중요!)시간복잡도를 낮춰주기 위한 힙!-우선순위큐
import heapq
#여기서 힙을 쓰므로써 매번 방분하지 않은 노드에 대해서 선형탐색으로
#매번 찾아줘야 하는 것이 아닌 그냥 heapq에서 뽑아냄으로써
#제일 거리가 짧은 노드에 대하여 알수있다(heapq의 특징)👨💻코드로 구현해주기
import heapq
import sys
input=sys.stdin.readline
#이렇게 sys에 대해서 해주는게 좋음 안그러면 백준같은데에서
#입력받다가 시간이 너무 느려져서 틀려버릴수도 있다
n,m=map(int,input().split())
#노드,간선의 수 정보 받기
start=int(input())
#출발노드에 대한 정보
INF=int(1e9)
distance=[INF]*(n+1)
graph=[[] for _ in range(n+1)]
for _ in range(m):
a,b,c=map(int,input().split())
graph[a].append((b,c))
#a에서 b로가는 비용이 c이다
#인접리스트
def dijkstra(start):
q=[]
heapq.heappush(q,(0,start))
#자기자신까지의 거리는 0,도착지점까지를 나타냄
distance[start]=0
while q:
dist,cur=heapq.heappop(q)
if distance[cur]<dist:
#이미 해당노드까지의 거리가 제일 짧다면 그냥 무시
continue
for next in graph[cur]:
cost=distance[cur]+next[1]
#여기서 next[1]은 인접리스트에서 비용을 의미
if cost<distance[next[0]]:
distance[next[0]]=cost
heapq.heappush(q,(cost,next[0])
시간복잡도는 O(ElogV)인거를 알 수 있다
즉 최소 간선의 횟수만큼 E만큼은 반복하게 되는 것을 알 수 있다.
왜냐하면 queue에 간선의 수만큼은 들어가게 되게 되기 때문이다
🖥(참고)무한대를 나타날때
종종 어떤 문제에서의 경우에서는 1e9를 넘어가는 경우가 존재한다 실제로
백준을 풀다가도 이러한 문제를 한 번 직면한 적이 있어서
이렇게 적어놓는다
차라리 1e9이런식이 좀 그렇다면
파이써닉한 방법으로 양의 무한대를 표현하면
positive=float("inf")
#양의 무한대
negative=float("-inf")
#음의 무한대