다익스트라 알고리즘

1. 개념

두 노드를 연결할 때, 가중치가 최소인 것을 구하는 알고리즘

 

2. 설명

1부터 시작할 때, minEdge[] 배열을 나타냈다.

 

각 노드를 탐색하면서 minEdge에 가중치를 누적 시킨다.

 

3. 문제

www.acmicpc.net/problem/1753

1753번: 최단경로

for문을 전부 탐색해서 최소 누적치를 찾는 풀이 -> 시간초과 때문에, 노드 수가 많으면 못 푼다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static class Edge{
		int v, w;
		public Edge(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}
	public static void main(String[] args) {
		//입력
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int K = sc.nextInt();
		int dist[] = new int[V];//노드까지의 최소 거리 저장
		Arrays.fill(dist, Integer.MAX_VALUE);
		ArrayList<Edge> list[] = new ArrayList[V]; 
		for (int i = 0; i < V; i++) {
			list[i]=new ArrayList<>();
		}
		for (int i = 0; i < E; i++) {
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			int w = sc.nextInt();
			list[u].add(new Edge(v, w));
		}
		boolean visit[] = new boolean[V];
		dist[K-1] = 0;
		for (int i = 0; i < V; i++) {
			//dist값이 젤 작은 정점의 번호를 찾으시오
			int min=Integer.MAX_VALUE;
			int index = -1;
			//가장 짧은 시작점을 찾고
			for (int j = 0; j < V; j++) {					
				if(!visit[j] && min > dist[j]) {
					min = dist[j];
					index = j;
				}
			}
			if(index == -1) break;
			//시작 정점에 연결된 간선하고 지금까지 최소거리 하고 더했을때 더 값이 작다면 갱신한다
			for (Edge next : list[index]) {
				if(!visit[next.v] && dist[next.v] > dist[index] + next.w) {
					dist[next.v] = dist[index] + next.w;
				}
			}
			visit[index] = true;
		}
		for (int k : dist) {
			if(k==Integer.MAX_VALUE) {
				System.out.println("INF");
			}else {
				System.out.println(k);
			}
		}
	}
}

 이 부분을 우선순위 큐로 바꿀 필요가 있다.

			for (int j = 0; j < V; j++) {					
				if(!visit[j] && min > dist[j]) {
					min = dist[j];
					index = j;
				}
			}

 

 

우선순위 큐를 사용 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static class Edge implements Comparable<Edge> {
		int no;
		int w;// total weight

		public Edge(int to, int w) {
			this.no = to;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return this.w - o.w;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int startidx = sc.nextInt();
		ArrayList<Edge> map[] = new ArrayList[V + 1];
		for (int i = 1; i <= V; i++) {
			map[i] = new ArrayList<>();
		}
		int minEdges[] = new int[V + 1];
		boolean visit[] = new boolean[V + 1];
		Arrays.fill(minEdges, Integer.MAX_VALUE);
		minEdges[startidx] = 0;

		for (int i = 0; i < E; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			map[u].add(new Edge(v, w));
		}
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(startidx, 0));
		while (!pq.isEmpty()) {
			Edge cur = pq.poll();
			if (visit[cur.no])
				continue;
			visit[cur.no] = true;

			for (Edge next : map[cur.no]) {
				if (!visit[next.no] && minEdges[next.no] > next.w + minEdges[cur.no]) {
					minEdges[next.no] = next.w + minEdges[cur.no];
					pq.add(new Edge(next.no, minEdges[next.no]));
				}
			}
		}
		for (int i = 1; i <= V; i++) {
			if (minEdges[i] == Integer.MAX_VALUE)
				System.out.println("INF");
			else
				System.out.println(minEdges[i]);
		}
	}
}
//priorityqueue<Edge>
	//q.add(add(index, weight))
	//while !q.isempty
		//Edge cur = q.poll
		//for Edge next : map[cur.no]
			//if !visit and minEdge[next.no] > cur.w + minEdge[cur.no]
				//minEdge[next.no] = cur.w + minEdge[cur.no]
				//pq.add next.no, minEdge[next.no]

 

우선순위큐를 위해 Comparable구현

	static class Edge implements Comparable<Edge> {
		int no;
		int w;// total weight

		public Edge(int to, int w) {
			this.no = to;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return this.w - o.w;
		}
	}

 

시작값 설정

PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(startidx, 0));

 

방문을 하지 않고, 다음 노드까지의 누적치 > 현재노드 가중치 + 현재노드 누적치 조건이 성립하면 변수 갱신

if (!visit[next.no] && minEdges[next.no] > next.w + minEdges[cur.no]) {
    minEdges[next.no] = next.w + minEdges[cur.no];
    pq.add(new Edge(next.no, minEdges[next.no]));
}