공부방
프림/다익스트라 알고리즘 본문
프림 알고리즘
- 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
- 임의 정점을 하나 선택해서 시작
- 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
- 모든 정점이 선택될 때까지 1. ,2. 과정을 반복
반복문
package day0330_프림_다익스트라;
import java.util.Arrays;
import java.util.Scanner;
public class 프림_반복문 {
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
// Scanner sc = new Scanner(System.in);
Scanner sc = new Scanner(input);
int V = sc.nextInt(); //V : 정점의 개수, 0부터 시작 한다!
int E = sc.nextInt(); //E : 간선의 수
int[][] adjArr = new int[V][V];
for(int i = 0 ; i<E; i++) {
int A = sc.nextInt(); //시작정점
int B = sc.nextInt(); //도착정점
int W = sc.nextInt(); //가중치
//무향 그래프 이니까
adjArr[A][B] = W;
adjArr[B][A] = W;
}//입력끝
//방문처리를 하기 위해서
boolean[] visited = new boolean[V];
int[] p = new int[V]; //내가 어디에서 왔는지에 대한 정보를 저장
int[] dist = new int[V]; //key라고 불리었던 가장 작은값을 저장하는 용도
//dist는 아주 아주 큰 값으로 갱신을 해라~
for(int i = 0 ; i<V; i++)
dist[i] = INF;
Arrays.fill(dist, INF);//위나 얘나 똑같다 동작은.
//임의의 한점을 선택해서 돌려야한다.
dist[0] = 0; //0번 정점을 가지고 시작할꺼야~
p[0] = -1; //
int ans = 0;
//프림을 동작시키겠다. 정점 개수만큼 돌아도 딱히 상관은 없다만 굳이?
for(int i = 0 ; i <V-1; i++) {
//1. 내가 가장 작은 값을 뽑겠다.
int min = INF;
int idx = -1;
//아직 안뽑힌 친구들 중 가장 작은 값을 뽑겠다.
for(int j = 0; j<V; j++) {
if(!visited[j] && dist[j] < min) {
min = dist[j];
System.out.println(min);
idx = j;
System.out.println(idx);
}
}//idx에는 가장 작은 값을 가지고 있는 정점이 뽑혔다.
visited[idx] = true; //선택!
//2. 뽑은 정점을 이용해서 갱신할 수 있는게 있다면 모조리 갱신
//인접 행렬이니까 모든 정점을 확인을 하는것
for(int j = 0 ; j<V; j++) {
if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
dist[j] = adjArr[idx][j];
p[j] = idx;
System.out.println(dist[j]);
System.out.println(p[j]);
}
}
}
for(int i = 0 ; i<V; i++) {
ans += dist[i];
}
System.out.println(ans);
}
static String input = "7 11\r\n" +
"0 1 32\r\n" +
"0 2 31\r\n" +
"0 5 60\r\n" +
"0 6 51\r\n" +
"1 2 21\r\n" +
"2 4 46\r\n" +
"2 6 25\r\n" +
"3 4 34\r\n" +
"3 5 18\r\n" +
"4 5 40\r\n" +
"4 6 51\r\n" +
"\r\n";
}
//
175우선순위큐
package day0330_프림_다익스트라;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class 프림_우선순위큐 {
static final int INF = Integer.MAX_VALUE;
static class Edge implements Comparable<Edge>{
int st, ed, w;
public Edge(int st, int ed, int w) {
this.st = st;
this.ed = ed;
this.w = w;
}
@Override
public int compareTo(Edge o) {
// return this.w - o.w;
return Integer.compare(this.w, o.w);
}
}
public static void main(String[] args) {
// Scanner sc = new Scanner(System.in);
Scanner sc = new Scanner(input);
int V = sc.nextInt(); //V : 정점의 개수, 0부터 시작 한다!
int E = sc.nextInt(); //E : 간선의 수
//인접리스트
List<Edge>[] adjList = new ArrayList[V];
//실제 담을 수 있는 바구니 준비
for(int i = 0 ; i<V; i++) {
adjList[i] = new ArrayList<>();
}
for(int i = 0 ; i<E; i++) {
int A = sc.nextInt(); //시작정점
int B = sc.nextInt(); //도착정점
int W = sc.nextInt(); //가중치
adjList[A].add(new Edge(A, B, W));
adjList[B].add(new Edge(B, A, W));
}//입력끝
//방문처리를 하기 위해서
boolean[] visited = new boolean[V];
PriorityQueue<Edge> pq = new PriorityQueue<>();
//시작정점을 하나 뽑고 할래
visited[0] = true;
// for(int i = 0 ; i<adjList[0].size(); i++) {
// pq.add(adjList[0].get(i));
// }
//
// for(Edge e : adjList[0]) {
// pq.add(e);
// }
pq.addAll(adjList[0]);
int pick = 1; //확보한 정점의 개수
int ans = 0 ;
// pick < V 이럴때 돌아~~
while(pick != V) {
Edge e = pq.poll();
if(visited[e.ed]) continue;
ans += e.w;
pq.addAll(adjList[e.ed]);
visited[e.ed] = true;
pick++;
}
System.out.println(ans);
}
static String input = "7 11\r\n" +
"0 1 32\r\n" +
"0 2 31\r\n" +
"0 5 60\r\n" +
"0 6 51\r\n" +
"1 2 21\r\n" +
"2 4 46\r\n" +
"2 6 25\r\n" +
"3 4 34\r\n" +
"3 5 18\r\n" +
"4 5 40\r\n" +
"4 6 51\r\n" +
"\r\n";
}
//
175다익스트라 알고리즘
- 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
- 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.
- 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다.
- 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로 구성된다.
다익스트라 알고리즘 활용
다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 찾는 문제를 해결하기 위해 사용됩니다. 다익스트라 알고리즘은 다음과 같은 경우에 사용할 수 있습니다:
단일 출발점 최단 경로 문제, 가중치가 있는 그래프, 음수 가중치가 없는 그래프, 최단 경로가 여러 개인 경우
동작 과정
- 시작 정점을 입력 받는다.
- 거리를 저장할 D배열을 무한대로 초기화한 후 시작점에서 갈 수 있는 곳의 값은 바꿔 놓는다.
- 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치의 합이 작다면 변경하여 적는다.
- 모든 정점을 방문할 때까지 반복
다익스트라 반복문 구현
package day0330_프림_다익스트라;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class 다잌스트라_반복문 {
static class Node {
int v, w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
}
static final int INF = Integer.MAX_VALUE;
static int V, E; //V : 정점 , E: 간선
static List<Node>[] adjList; //인접리스트
static int[] dist; //최단 길이를 저장할 배열
public static void main(String[] args) {
Scanner sc = new Scanner(input);
V = sc.nextInt();
E = sc.nextInt();
adjList = new ArrayList[V];
for(int i = 0 ; i<V; i++)
adjList[i] = new ArrayList<>();
dist = new int[V];
Arrays.fill(dist, INF);
//입력 받기
for(int i = 0 ; i<E; i++) {
int A = sc.nextInt();
int B = sc.nextInt();
int W = sc.nextInt();
//유향 그래프였다.
adjList[A].add(new Node(B, W)); //인접리스트 노드 추가
//아래의 한줄 코드가 위의 4줄을 커버하지만 익숙치 않은 상황이라면 자제할것
// adjList[sc.nextInt()].add(new Node(sc.nextInt(), sc.nextInt()));
}
dijkstra(0);
System.out.println(Arrays.toString(dist));
}
private static void dijkstra(int start) {
boolean[] visited = new boolean[V];
dist[start] = 0; //시작 노드까지의 거리는 0
for(int i = 0 ; i< V-1; i++) {
int min = INF;
int idx = -1;
//선택하지 않은 정점 중 dist가 가장 짧은 것을 골라
for(int j = 0; j<V; j++) {
if(!visited[j] && min > dist[j]) {
min = dist[j];
idx = j;
}
}
if(idx == -1) break; //선택할 친구가 없다.
visited[idx] = true; //선택
//갱신할 수 있으면 갱신
// 이방법이 조금더 좋으면 사용할 것
// for(Node node : adjList[idx]) {
//
// }
for(int j = 0 ; j< adjList[idx].size(); j++) {
Node curr = adjList[idx].get(j);
//방문하지 않았고, 연결도되었고(인접행렬일때나 해당됨),
//이미 가지고 있는 값보다 더 굉장한 값이 이싿면 갱신
if(!visited[curr.v] && dist[curr.v]> dist[idx] + curr.w )
dist[curr.v]= dist[idx] + curr.w;
}
}
}
static String input = "6 11\r\n" + "0 1 4\r\n" + "0 2 2\r\n" + "0 5 25\r\n" + "1 3 8\r\n" + "1 4 7\r\n"
+ "2 1 1\r\n" + "2 4 4\r\n" + "3 0 3\r\n" + "3 5 6\r\n" + "4 3 5\r\n" + "4 5 12\r\n" + "";
}
//
[0, 3, 2, 11, 6, 17]우선순위 큐 구현
- Edge 클래스: 이 클래스는 간선을 나타냅니다. 각 간선은 목적지 정점(ed)과 가중치(w)를 가집니다. 이 클래스는 또한 가중치를 기준으로 간선을 비교하기 위해 compareTo 메서드를 구현합니다.
- main 메서드: 이 메서드는 프로그램의 실행을 담당합니다. 먼저, 사용자로부터 정점의 수(V)와 간선의 수(E)를 입력받습니다.
- 인접 리스트 adjList를 초기화하고 사용자로부터 간선 정보를 입력받아 인접 리스트에 추가합니다.
- visit 배열은 방문한 정점을 추적하고, distances 배열은 시작 정점에서 각 정점까지의 최단 거리를 저장합니다. 배열을 초기화한 후, 시작 정점의 거리를 0으로 설정합니다.
- 우선순위 큐 pq를 생성하고 시작 정점을 추가합니다. 이 큐는 정점을 처리할 때 거리를 기준으로 정렬합니다.
- 큐가 비어있지 않은 동안 다음을 반복합니다: a. 큐에서 가장 가까운 정점을 꺼냅니다. b. 이미 방문한 정점이면 무시하고 다음 반복으로 넘어갑니다. c. 정점을 방문 처리하고 인접한 간선들을 검사합니다. 방문하지 않은 정점에 대해서만 최단 거리를 업데이트하고, 업데이트된 거리를 가진 정점을 우선순위 큐에 추가합니다.
- 모든 정점이 처리되면, 시작 정점에서 각 정점까지의 최단 거리를 출력합니다.
package day0330_프림_다익스트라;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class 다잌스트라_우선순위큐 {
static final int INF = Integer.MAX_VALUE;
// Edge 클래스에서 시작 정점(st) 필드를 제거합니다.
static class Edge implements Comparable<Edge> {
int ed, w;
public Edge(int ed, int w) {
this.ed = ed;
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();
List<Edge>[] adjList = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
int A = sc.nextInt();
int B = sc.nextInt();
int W = sc.nextInt();
adjList[A].add(new Edge(B, W));
// adjList[B].add(new Edge(A, W)); //무향이면 추가
}
boolean[] visit = new boolean[V];
// distances 배열을 추가하여 시작 정점에서 각 정점까지의 최단 거리를 저장합니다.
int[] distances = new int[V];
Arrays.fill(distances, INF);
distances[0] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(0, 0));
while (!pq.isEmpty()) {
Edge curEdge = pq.poll();
int cur = curEdge.ed;
// 이미 방문한 정점이면 무시합니다.
if (visit[cur]) {
continue;
}
// 방문하지 않은 정점이면 방문 처리를 합니다.
visit[cur] = true;
for (Edge nextEdge : adjList[cur]) {
int next = nextEdge.ed;
int weight = nextEdge.w;
// 방문하지 않은 정점에 대해서만 최단 거리를 업데이트합니다.
if (!visit[next] && distances[cur] + weight < distances[next]) {
distances[next] = distances[cur] + weight;
pq.add(new Edge(next, distances[next]));
}
}
}
// 결과 출력 부분에서 시작 정점에서 각 정점까지의 최단 거리를 출력합니다.
System.out.println("Shortest distances from vertex 0 to all other vertices:");
for (int i = 0; i < V; i++) {
System.out.println("Vertex " + i + ": " + distances[i]);
}
}
}
'알고리즘/그래프' Related Articles
more
