최단 경로를 구하는 알고리즘
- BFS
- 가중치가 모두 1일때
- 시간 복잡도 O(V+E)
- 한점에서 시작할 수 있음
2. 다익스트라
- 가중치가 0이상 일때
- 시간복잡도 O(ElogV)
- 한점에서 시작할 수 있음
- 우선순위 큐 사용
=> 시작점에서 모든점까지의 최단거리 구하기
(매번 방문하지 않은 노드중에서 최단거리가 가장 짧은 노드를 선택하여 한단계씩 최단거리를 구해나간다)
- 플로이드 워샬
- 가중치 제한 없음
- 시간복잡도 O(V^3) =>3중 반복문으로 구현한다.
- 모든점에서 시작할 수 있음
=> 모든 정점에서 모든 정점으로의 최단거리
3
- 벨만포드
- 가중치 제한 없음 (음수 간선이 있을때)
- 시간복잡도 O(V*E)
- 한점에서 시작할 수 있음
=> 시작점에서 모든점까지의 최단거리
(매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다)
마지막 노드에서는 dist 갱신이 되면 안되기 때문에 마지막 노드에서 dist가 갱신되면 사이클이 있다고 판단한다.
정점의 개수만큼 for문돌고 안에서 간선의 개수만큼 또 for문 돈다 그래서 시간복잡도 O(V*E)
다익스트라
우선순위 큐 (Priority Queue)
우선 순위가 높은 데이터가 먼저 나오는 큐
보통 힙을 이용하여 구현된다.
힙 (Heap)
완전 이진 트리의 일종(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리)
- 최솟값과 최댓값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 부모 노드의 키 값이 항상 자식노드의 키값보다 작거나 큰 이진트리이다.(최소 힙, 최대 힙)
JAVA에서 PriorityQueue
- 선언
//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());- 메소드
추가 : add, offer
삭제 : poll(첫번째 값 반환 후 제거), remove(그냥 제거), clear (초기화)
peek() : 우선순위가 가장 높은 값 출력
다익스트라 매커니즘
- 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다. (그리디)
- 해당 노드로 부터 갈 수 있는 노드들의 비용을 갱신한다.(dp)
문제 풀이
백준 18352 : 특정 거리의 도시 찾기
문제
1~N까지의 도시와 M개의 도로(단방향)
도시 X에서 출발하여 도달할수 있는 모든 도시 중에서 최단 거리가 K인 도시의 번호 출력
입력
도시의 갯수 N, 도로의 개수 M, 최단거리 K, 출발도시의 번호 X
A->B (M줄)
출력
최단 거리가 K인 도시 번호 한줄의 한개씩 오름차순 출력
하나도 없으면 -1 출력
코드
import java.util.*;
public class 백준18352 {
static class Info implements Comparable<Info>{
int idx, distance; //인덱스와 가중치를 저장한다.
Info(int idx,int distance){
this.idx=idx;
this.distance=distance;
}
public int compareTo(Info other) { //가중치를 기준으로 comparable을 선언하여 우선순위 큐의 판단 기준을 제공한다.
if(this.distance<other.distance) {//비교할 값보다 지금이 최소값일 때 -> 교환안함
return -1; //음수 일경우 : 교환안함
}
return 1;
}
}
static Scanner scan=new Scanner(System.in);
static int n,m,k,x,ans=0;
static int[] dist;
static boolean [] visited;
static ArrayList<ArrayList<Info>> list=new ArrayList<>();
public static void main(String[] args) {
/////////////////입력/////////////////////////
n=scan.nextInt(); //도시의 갯수
m=scan.nextInt(); //도로의 갯수
k=scan.nextInt(); //최단거리
x=scan.nextInt(); //출발도시
dist=new int[n+1]; //최단 경로 저장용 배열
//리스트 초기화
for(int i=1;i<=n+1;i++) {
list.add(new ArrayList<>());
}
for(int i=0;i<m;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
list.get(a).add(new Info(b,1));
}
/////////////////초기화/////////////////////////
//모든 정점까지의 거리를 무한대로 초기화 해주기
//최소값인지 비교해서 갱신해주어야하기 때문에 초기값은
for(int i=0;i<=n;i++) {
dist[i]=Integer.MAX_VALUE;
}
dist[x]=0; //출발도시는 0으로 초기화
////다익스트라 시작////
dijkstra(x);
for(int i=1;i<dist.length;i++) {
int distance=dist[i];
if(distance==k) {
System.out.println(i);
ans++;
}
}
if(ans==0) {
System.out.print(-1);
}
}
static void dijkstra(int start) {
//최소 힙 생성
PriorityQueue<Info> pq=new PriorityQueue<>();
pq.add(new Info(start,0)); //출발 노드 wieght(가중치) 0으로 초기화
//거리 정보들이 소진 될때까지 거리를 갱신한다.
while(!pq.isEmpty()) {
Info info =pq.poll(); //우선순위가 가장 높은 것을 꺼내서 (여기서 우선순위는 distance = 다 1이므로 같음)
int index=info.idx;
int distance=info.distance;
if(dist[index]<distance) { //꺼낸 정보가 최신 정보랑 다르면 의미 없으므로 폐기 한다 (예 :1->2->3 가는경우)
continue;
}
for(int i=0;i<list.get(index).size();i++) { //해당 도시와 연결되어있는 도시를 탐색
int index2=list.get(index).get(i).idx;
int distance2=list.get(index).get(i).distance+distance; //index까지의 distance와 i까지의 distance를 더한 값
if(dist[index2]>distance2) { //새로운 distance(distance2)와 기존 distance 비교
dist[index2]=distance2; //갱신 ( 초기값은 무한대이므로 처음엔 무조건 갱신됨)
pq.add(new Info(index2,distance2)); //priority queue에 삽입
}
}
}
}
}문제
백준 1916 최소비용 구하기
풀이
위의 코드와 같이 다익스트라를 사용한다.
입력만 변경하면 된다.
코드
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class 백준1916 {
static class Info implements Comparable<Info>{
int idx, distance; //인덱스와 가중치를 저장한다.
Info(int idx,int distance){
this.idx=idx;
this.distance=distance;
}
public int compareTo(Info other) { //가중치를 기준으로 comparable을 선언하여 우선순위 큐의 판단 기준을 제공한다.
if(this.distance<other.distance) {//비교할 값보다 지금이 최소값일 때 -> 교환안함
return -1; //음수 일경우 : 교환안함
}
return 1;
}
}
static Scanner scan=new Scanner(System.in);
static int n,m,k,x,ans=0;
static int[] dist;
static boolean [] visited;
static ArrayList<ArrayList<Info>> list=new ArrayList<>();
public static void main(String[] args) {
/////////////////입력/////////////////////////
n=scan.nextInt(); //도시의 개수
m=scan.nextInt(); //버스의 개수
dist=new int[n+1]; //최단 경로 저장용 배열
//리스트 초기화
for(int i=1;i<=n+1;i++) {
list.add(new ArrayList<>());
}
for(int i=0;i<m;i++) {
int a=scan.nextInt(); //출발 도시 번호
int b=scan.nextInt(); //도착 도시 번호
int c=scan.nextInt(); //버스 비용
list.get(a).add(new Info(b,c));
}
int start =scan.nextInt();
int end=scan.nextInt();
/////////////////초기화/////////////////////////
//모든 정점까지의 거리를 무한대로 초기화 해주기
//최소값인지 비교해서 갱신해주어야하기 때문에 초기값은
for(int i=0;i<=n;i++) {
dist[i]=Integer.MAX_VALUE;
}
dist[start]=0; //출발도시는 0으로 초기화
////다익스트라 시작////
dijkstra(start);
System.out.print(dist[end]);
}
static void dijkstra(int start) {
//최소 힙 생성
PriorityQueue<Info> pq=new PriorityQueue<>();
pq.add(new Info(start,0)); //출발 노드 wieght(가중치) 0으로 초기화
//거리 정보들이 소진 될때까지 거리를 갱신한다.
while(!pq.isEmpty()) {
Info info =pq.poll(); //우선순위가 가장 높은 것을 꺼내서 (여기서 우선순위는 distance = 다 1이므로 같음)
int index=info.idx;
int distance=info.distance;
if(dist[index]<distance) { //꺼낸 정보가 최신 정보랑 다르면 의미 없으므로 폐기 한다 (예 :1->2->3 가는경우)
continue;
}
for(int i=0;i<list.get(index).size();i++) { //해당 도시와 연결되어있는 도시를 탐색
int index2=list.get(index).get(i).idx;
int distance2=list.get(index).get(i).distance+distance; //index까지의 distance와 i까지의 distance를 더한 값
if(dist[index2]>distance2) { //새로운 distance(distance2)와 기존 distance 비교
dist[index2]=distance2; //갱신 ( 초기값은 무한대이므로 처음엔 무조건 갱신됨)
pq.add(new Info(index2,distance2)); //priority queue에 삽입
}
}
}
}
}
남기고 싶은 개발자입니다 :>