🧚‍♂️알고리즘🧚‍♂️ - 그래프 - 다익스트라

Dijkstra Algorithm

그래프에서 최단 거리를 구하는 알고리즘

특정 노드에서 다른 노드들의 최단 거리 구하기

기능

• 출발 노드와 모든 노드 간의 최단 거리 탐색

특징

• 에지가 모두 양수

 시간 복잡도

• O(에지 수*log(노드수))

헉헉 만드느라 힘들엇다(이독멘토링자료)

최단거리 구하기이기 때문에

BFS와 상당히 유사 (큐 이용/방문리스트활용)

그 세부 버전 같기도(최단거리 계산 추가된)

---

🥇골드5

1753번: 최단경로

1) 거리 리스트에서 방문하지 않은, 현재 값이 가장 작은 노드 선택
2) 해당 노드와 연결된 노드들의 최단 거리 값을 업데이트 ( 선택 노드의 리스트값+에지 가중치, 현재 값 중에서 작은 것)
큐가 빌 때까지 반복하기
3) 큐가 빌 때까지 1-2 반복

+최대값!

sys.maxsize

from queue import PriorityQueue #우선순위 큐
import sys
V,E = map(int,sys.stdin.readline().split()) #정점의 개수 V와 간선의 개수 E
K = int(sys.stdin.readline()) #시작 정점의 번호 K

result = [sys.maxsize] * (V+1) #최단거리결과리스트
visited = [False]* (V+1) #방문리스트
nearList = [[] for _ in range(V+1)] #인접리스트 + 가중치
Myqueue = PriorityQueue() # 왜냐면,,,,왜?

#인접리스트+가중치 저장 
for _ in range(E):
    u,v,w = map(int,sys.stdin.readline().split()) # u에서 v로 가는 가중치 w인 간선
    nearList[u].append((v,w))
#시작점 설정하기
Myqueue.put((0,K)) #put/get
result[K] = 0

#탐색시작
while Myqueue.qsize() > 0:
    Now = Myqueue.get() #첫번째 요소(거리)의 크기대로 항상 정렬
    nowNode = Now[1]
    #방문확인(처음도착 다음의 도착은 무조건 더 길으므로)
    if visited[nowNode]:
        continue
    visited[nowNode] = True
    #인접노드 확인
    for cha in nearList[nowNode]:
        nextNode = cha[0]
        plusdis = cha[1]
        if result[nextNode] > result[nowNode] + plusdis:#최소거리업데이트
            result[nextNode] =result[nowNode] + plusdis
            Myqueue.put((result[nextNode],nextNode)) #변경 전이 더 컸으면 다시 확인해볼 필요 없음

#결과
for i in range(1,V+1):
    if visited[i]:
        print(result[i])
    else:
        print("INF")#도달할 수 없는 노드

왜 우선순위 큐를 사용해야 하는지 잘 이해를 못하겠다.

여러 경로가 있을 수 있는데 노드를 다시 방문할 수 없으므로 개중 가장 짧은 것을 알기 위해..? 하는 건가..?

글 읽기 - 왜 우선순위 큐를 사용해야 하는지..??????ㅜㅜ

차례대로 하나씩 최소 거리를 확정하는 것이기 때문(노드 get 시 확정!)

get한 노드 중심으로 연결 노드들의 값을 갱신(더 최소일 시)하여 더 최소로 만드려고 하므로

우선순위 큐를 이용하여 제일 최소 값을 확정시키고 나머지도 더 적어질 여지가 있는지 확인하는 것!

---

🥇골드5

1916번: 최소비용 구하기

위 문제와 거의 일치한다.

그냥 모든 최단거리가 아니라 하나의 최단거리만 출력하면 됨

from queue import PriorityQueue #우선순위 큐
import sys
V = int(sys.stdin.readline()) #도시
E = int(sys.stdin.readline()) #버스

result = [sys.maxsize] * (V+1) #최단거리결과리스트
visited = [False]* (V+1) #방문리스트
nearList = [[] for _ in range(V+1)] #인접리스트 + 가중치
Myqueue = PriorityQueue() # 왜냐면,,,,왜?

#인접리스트+가중치 저장 
for _ in range(E):
    u,v,w = map(int,sys.stdin.readline().split()) # u에서 v로 가는 가중치 w인 간선
    nearList[u].append((v,w))

K,F = map(int,sys.stdin.readline().split()) #시작 / 끝
#시작점 설정하기
Myqueue.put((0,K)) #put/get
result[K] = 0

#탐색시작
while Myqueue.qsize() > 0:
    Now = Myqueue.get() #첫번째 요소(거리)의 크기대로 항상 정렬
    nowNode = Now[1]
    #방문확인(처음도착 다음의 도착은 무조건 더 길으므로)
    if visited[nowNode]:
        continue
    visited[nowNode] = True
    #인접노드 확인
    for cha in nearList[nowNode]:
        nextNode = cha[0]
        plusdis = cha[1]
        if result[nextNode] > result[nowNode] + plusdis:#최소거리업데이트
            result[nextNode] =result[nowNode] + plusdis
            Myqueue.put((result[nextNode],nextNode)) #변경 전이 더 컸으면 다시 확인해볼 필요 없음

#결과
print(result[F])

---

✳️플래티넘 4

1854번: K번째 최단경로 찾기

어떻게 최단 경로가 아닌 "K"번째 최단 경로를 찾을 수 있을까??

 

+ 다익스트라 알고리즘에서해당 노드를 다시 사용하지 않도록 설정하는 부분은 삭제가 필요함.

+ 최단 거리 리스트를 k개의 열을 갖도록 초기화함

 

- 우선순위 큐에서 연결된 노드와 가중치 데이터를 pop

- 연결 노드의 k번째 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 업데이트 / 이때 거리 배열을 오름차순으로 정렬하고 유선순위 큐에 연결 노드를 추가

- 위 단계를 우선순위 큐가 비워질 때까지 반복 

- 결과 리스트를 탐색하며 k번째 경로가 무한대면 -1 출력 / 그 외는 해당 경로값 출력

 

+heapq / priorityqueue

[Python/파이썬] PriorityQueue & heapq / 우선순위큐와 힙큐

우선순위 큐를 heapq로 구현하는 방법 숙지하기

import heapq #우선순위 큐
import sys
N,M,K = map(int,sys.stdin.readline().split())
nearList= [[] for _ in range(N+1)] #노드정보
distance = [[sys.maxsize]*K for _ in range(N+1)] #거리 리스트를 큰 값으로, K개

#인접리스트+가중치 저장 
for _ in range(M):
    a,b,c = map(int,sys.stdin.readline().split()) # u에서 v로 가는 가중치 w인 간선
    nearList[a].append((b,c))

#시작점 설정하기
pq = [(0,1)] #가중치 우선 우선순위 큐
distance[1][0] = 0 # 출발 노드

#변형 다익스트라 탐색시작
while pq:
    c, n = heapq.heappop(pq)
    for nN, nC in nearList[n]:
        if distance[nN][K-1] > c + nC:
            distance[nN][K-1] = c + nC
            distance[nN].sort()
            heapq.heappush(pq,(c + nC,nN))

#결과
for i in range(1, N+1):
    if distance[i][K-1] == sys.maxsize: #도달불가
        print(-1)
    else:
        print(distance[i][K-1])

모오든 경로를 다 탐색하는..

건가??

아악

나중에 한번 더 혼자 풀어야지