최단 경로 알고리즘
최단 경로 알고리즘이란 두 노드를 잇는 가장 짧은 경로를 찾는 것.
가중치가 기재된 그래프 형태에서 Edge의 합이 최소가 되도록 하는 경로를 구하는 것.
로직
출발 노드를 기점으로 연결되 있는 정점들을 추가해가며 최단 거리를 계산
우선순위 큐 활용
우선순위 큐 사용시 노드 간의 간선 길이가 가장 짧은 노드와 해당 노드의 길이를 추출 할 수 있음.
초기 첫 정점의 거리는 자기 자신과의 거리는 없기에 0 으로 설정
그리고 나머지 노드끼리의 간선 길이는 infinite(inf) 로 설정.
우선순위 큐에 첫 정점의 정보만 넣음 (거리 0)
첫 노드를 큐에서 꺼내면서 연결되 있는 노드 와의 거리를 계산
만약에 최초에 초기화된 혹은 기존에 연결돼 있는 간선끼리의 합이 꺼내진 노드와의 거리의 합보다 크면 새롭게 꺼내진 노드와의 간선길이 합의 값으로 새로 설정.
간선 길이가 업데이트 되면 우선 순위 큐에 삽입
-> 기존의 길이보다 더 짧은 노드를 찾았기에 목표점이 짧은 노드로 변경 되고 해당 노드와 또 다른 연결된 노드와의 간선길이를 보고 싶게 됨 !
반대로, 큐에 새롭게 들어온 노드와 연결되 있는 다른 노드와의 길이가 기존의 간선길이 합보다 더 크면 계산에 넣지 않음 즉, 큐에 넣지 않음.
다음의 과정을 큐가 빌 때 까지 무한 반복 !
우선순위 큐
우선순위 큐는 들어갈 때 (push) 는 작은 순서대로 들어가진 않지만
pop 시킬 때는 작은 값 부터 추출됨
그래프 그리기
코드
1) heapq import
2) 우리의 목적은 "최단 경로" 를 찾는 것이니 무한한 값으로 초기 설정해 우리가 점점 작은 값을 찾으면 찾을수록 업데이트 해주기
3) 첫번째 노드에서의 간선길이는 없으므로 0으로 설정
4) 빈 리스트(queue)를 불러오고,
5) queue에 start (첫 시작 노드)의 간선길이와 노드 이름을 넣어준다
6) 큐가 빌 때 까지,
7) 이제 하나씩 큐에서 빼가면서 최단 경로를 찾아준다.
8) 처음에는 current_node => 'A' , current_distance = 0 이다.
9) if문으로 가기 전에
10) graph[current_node] 즉, A와 연결된 노드를 찾고
11) 연결된 노드의 이름과 간선길이를 adjacent, weight으로 받는다.
12) 그리고 최단 경로를 찾아주기 위해 distance는 현재 노드 까지의 길이와 새롭게 연결된 노드까지의 합으로 설정
13) 근데 만약에 기존의 경로보다 더 짧은 경로를 찾았으면
14) 해당 노드까지의 길이는 짧은 경로로 설정 !
15) 그리고 큐에 업데이트된 노드와 이때까지의 간선 길이를 넣어줌
- 위에서 9번의 if문은 13번과는 반대되는 상황으로 업데이트를 해줄 필요가 없는 즉 기존의 경로보다 더 짧은 상황이 아니기에 continue.
시간복잡도
크게 2가지의 과정으로 이루어짐
1) 간선 여행 -> 노드와 노드끼리 연결된 간선은 다 지나가야함 ( O(E) )
2) 우선 순위 큐에서의 삽입,삭제 -> 최악은 가는 노드마다 최단 거리여서 큐에 삽입,삭제를 존재하는 간선 만큼 수행 (O(E)) 또한 O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 𝑂(𝑙𝑜𝑔𝐸) 가 걸림 따라서 𝑂(𝐸𝑙𝑜𝑔𝐸)
1),2) 과정을 더해주면 O(E) + 𝑂(𝐸𝑙𝑜𝑔𝐸) = 𝑂(𝐸+𝐸𝑙𝑜𝑔𝐸)=𝑂(𝐸𝑙𝑜𝑔𝐸)
