최단거리 알고리즘이란?
가중 그래프 상 두 노드를 연결하는 가장 짧은 경로를 연결하는 알고리즘 .
EX) 지도 경로 탐색, 네트워크 구축등에 드는 비용을 최소화하는데 이용.
다익스트라 알고리즘
- 출발점에서 목표점까지 최단경로를 구하는 알고리즘.
- 한 노드에서 다른 모든 노드로의 최단 경로를 구할수 있다.
- 음의 간선이 없어야한다.
- 셋중에 가장빠름.
- O((V+E)log V)의 시간복잡도
이 두가지를 가지고 알고리즘을 적용.
(1) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다(그리디 알고리즘).
(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다(다이나믹 프로그래밍).
dikstra for문
//1. 노드 클래스를 생성한다.
public static void dijkstra(int v, int[][] data, int start) {
ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
//2. 그래프 노드 생성
for (int i = 0; i < v + 1; i++) {
graph.add(new ArrayList<>());
}
//3. graph key => 노드 key 값
graph value => (어느노드로 가는지,가중치)
for (int i = 0; i < data.length; i++) {
graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
}
//4.메모리제이션 배열 생성
int[] dist = new int[v + 1];
//5.최댓값으로 초기화
for (int i = 1; i < v + 1; i++) {
dist[i] = Integer.MAX_VALUE;
}
//start는 0
dist[start] = 0;
//방문배열
boolean[] visited = new boolean[v + 1];
//6. 방문 안한 애들 중 메모리배열에 업데이트
for (int i = 0; i < v; i++) {
int minDist = Integer.MAX_VALUE;
int curIdx = 0;
//방문한적이 없고 , 거리가 짧은 애들을 업데이트
for (int j = 1; j < v + 1; j++) {
if (!visited[j] && dist[j] < minDist) {
// min_node와 연결된 노드들(방문하지 않은) distance 값을 갱신
// distance가 짧다면 갱신
minDist = dist[j];
curIdx = j;
}
}
visited[curIdx] = true;
//인접노드 몇개있는지 size
for (int j = 0; j < graph.get(curIdx).size(); j++) {
//해당 노드를 가져와서 거리 업데이트
Node adjNode = graph.get(curIdx).get(j);
// 현재거리와 비용이 더 작으면 업데이트
if (dist[adjNode.to] > dist[curIdx] + adjNode.weight) {
//거리정보 값보다, 현재거리, 거쳐가는 비용이 작다면 업데이트
dist[adjNode.to] = dist[curIdx] + adjNode.weight;
}
}
}
//출력
for (int i = 1; i < v + 1; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i] + " ");
}
}
}
dikstra 우선순위 큐
public static void dijkstra(int v, int[][] data, int start) {
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
//2. 그래프 노드 생성 노드번호가 1부터니깐 0은 나중에 안쓰기
for (int i = 0; i < v+1 ; i++) {
graph.add(new ArrayList<>());
}
//3. 그래프 키값 과 value를 넣어줌 다른노드로 얼마가 드는지
for (int i = 0; i < data.length; i++) {
graph.get(data[i][0]).add(new Node(data[i][1],data[i][2]));
}
//4.메모리제이션 배열 생성
int [] dist = new int [v+1];
//5.최댓값으로 초기화
for (int i = 1; i <v+1 ; i++) {
dist[i] = Integer.MAX_VALUE;
}
//start는 0
dist[start] =0;
//방문배열
// 최소간선 탐색 필요 없어짐 오름차순으로 정렬
PriorityQueue<Node> pq = new PriorityQueue<>((x,y) -> x.weight - y.weight);
pq.offer(new Node (start,0));
while(!pq.isEmpty()){
Node curNode = pq.poll();
//하나 뱉고
if(dist[curNode.to] < curNode.weight){
continue;
// 현재 distance 위치에 가중치가 작다면 넘어가자
}
for (int i = 0; i < graph.get(curNode.to).size(); i++) {
Node adjNode= graph.get(curNode.to).get(i);
if(dist[adjNode.to] > curNode.weight +adjNode.weight){
dist[adjNode.to] = curNode.weight +adjNode.weight;
pq.offer(new Node(adjNode.to,dist[adjNode.to]));
}
}
}
//출력
for (int i = 1; i < v+1; i++) {
if(dist[i]== Integer.MAX_VALUE){
System.out.print("INF ");
}else{
System.out.print(dist[i]+" ");
}
}
}
관련 문제
BOJ 1906 최소비용 구하기
static void dijkstra(int start) {
PriorityQueue<Node> q = new PriorityQueue<>((x,y)-> x.weight - y.weight);
Arrays.fill(dp,Integer.MAX_VALUE);
q.offer(new Node(start,0));
dp[start] =0;
while(!q.isEmpty()){
Node CurNode = q.poll();
int to = CurNode.to;
if(check[to]){
continue;
}
check[CurNode.to] =true;
for(Node next: graph[to]){
if(dp[next.to] >= dp[to]+next.weight){
dp[next.to] = dp[to]+next.weight;
q.add(new Node(next.to,dp[next.to]));
}
}
}
다익스트라 알고리즘이 어떻게 돌아가는지 알수 있는 최적의 문제라고 생각한다.
벨만-포드 알고리즘
음수간선이 포함되어 있어도 최단 경로를 구할 수 있음.
음수 사이클이 있으면 정상 동작하지 않음.
매번 모든 간선을 확인, 다익스트라에 비해느림.
초깃값을 0 을 넣네 여긴 다른거는 무한대 처리
초기노드에서 시작하는 간선만 값을 더해주고 나머지 CONTINUE 처리
public static void bellmanFord(int v, int e, int[][] data, int start) {
Edge[] edge =new Edge[e];
//간선 갯수만큼 그래프 생성
for (int i = 0; i < e; i++) {
edge[i] = new Edge(data[i][0],data[i][1],data[i][2]);
}
int [] dist = new int [v+1];
for (int i = 1; i < v+1 ; i++) {
dist[i] = Integer.MAX_VALUE;
}
dist[start] =0;
boolean inMinusCycle = false;
for (int i = 0; i < v+1; i++) {
for (int j = 0; j < e; j++) {
Edge cur = edge[j];
if(dist[cur.from] == Integer.MAX_VALUE){
//만약 해당 노드로 가는 가중치가 무한대면 넘어간다아
continue;
}
if(dist[cur.to] > dist[cur.from]+cur.weight){
// 이거 계속 이해가 안갔었는데
// 해당 노드로 이동할때 드는 가중치의 합이 최소값이어야 업데이트를 시켜준다는 말이어씀.
//빠르게 구할거면 다익스트라고 음수사이클있으면 벨만 포드 쓰면 되겠는데?
dist[cur.to] = dist[cur.from]+cur.weight;
if(i == v){
inMinusCycle =true;
}
}
}
}
System.out.println("음수사이클 여부"+ inMinusCycle);
for (int i = 1; i < v+1; i++) {
if(dist[i] == Integer.MAX_VALUE){
System.out.print("INF ");
}else{
System.out.print(dist[i]+" ");
}
}
}
관련 문제
https://www.acmicpc.net/problem/1865 웜홀
플로이드-와샬 알고리즘
모든 노드간의 최단경로 구하기
음의 간선이 있어도 사용가능.
음수사이클있으면 정상동작 x
O(v^3) 시간 복잡도
static int [][] dist;
static final int INF = 1000000000;
public static void floydWarshall(int v, int e, int[][] data, int start) {
dist = new int [v+1][v+1];
//그래프 생성
for (int i = 1; i < v+1 ; i++) {
for (int j = 1; j < v+1 ; j++) {
if(i != j){
dist[i][j] = INF;
}
}
}
//무한대로 초기화 N X N 아닐때
// 그래프에 값 입력
for (int i = 0; i < e; i++) {
dist[data[i][0]][data[i][1]] = data[i][2];
}
for (int i = 1; i <v+1 ; i++) {
// j=>k로 갈때 i를 거쳐서 가는 경우가 짧을 때 업데이트
for (int j = 1; j <v+1 ; j++) {
for (int k = 1; k <v+1 ; k++) {
if(dist[j][k] != INF && dist[k][i] !=INF){
dist[j][k] = Math.min(dist[j][k],dist[j][i]+dist[i][k]);
}
}
}
}
//출력
for (int i = 1; i < v+1 ; i++) {
for (int j = 1; j < v+1 ; j++) {
if(dist[i][j] >= INF){
System.out.printf("%5s ","INF");
}else{
System.out.printf("%5d ", dist[i][j]);
}
}
System.out.println();
}
}
관련 문제
풀스택개발자가 될래요