Chapter 9. 최단경로

다익스트라 최단 경로 알고리즘

1. 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
2. '음의 간선'이 없을때 정상적으로 동작한다.
3. 그리디 알고리즘으로 분리된다. (매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.)
4. '방문하지 않은 노드중에서 가장 최단 거리가 짧은 노드를 선택'하는 과정을 반복한다.
   1. 다익스트라 알고리즘이 진행되면서 '한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는 것으로 이해
   2. 마지막 노드는 확인할 필요 없음
5. 간단한 다익스트라 알고리즘의 시간복잡도 : O(V^2), V는 노드의 개수
6. 개선된 다익스트라 알고리즘의 시간복잡도 :  O(ElogV), E는 간선의 개수, V는 노드의 개수
   1. 우선순위 큐 사용 -> 우선순위가 높은 데이터를 먼저 삭제
   2. 거리가 가장 짧은 노드를 선택하기 위해서 는 우선순위큐에서 그냥 꺼내면된다.
   3. 한 번 처리된 노드는 더 이상 처리되지 않는다 때문에, 간단한 다익스트라 알고리즘보다 빠르다.

리스트로 사용하는법

import java.util.*;

class Node implements Comparable<Node> {

    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public int getIndex() {
        return this.index;
    }

    public int getDistance() {
        return this.distance;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Node other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int n, m, start;
    // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    // 최단 거리 테이블 만들기
    public static int[] d = new int[100001];

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while(!pq.isEmpty()) { // 큐가 비어있지 않다면
            // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
            Node node = pq.poll();
            int dist = node.getDistance(); // 현재 노드까지의 비용 
            int now = node.getIndex(); // 현재 노드
            // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            if (d[now] < dist) continue;
            // 현재 노드와 연결된 다른 인접한 노드들을 확인
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).getDistance();
                // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                if (cost < d[graph.get(now).get(i).getIndex()]) {
                    d[graph.get(now).get(i).getIndex()] = cost;
                    pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Node>());
        }

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
            graph.get(a).add(new Node(b, c));
        }

        // 최단 거리 테이블을 모두 무한으로 초기화
        Arrays.fill(d, INF);

        // 다익스트라 알고리즘을 수행
        dijkstra(start);

        // 모든 노드로 가기 위한 최단 거리를 출력
        for (int i = 1; i <= n; i++) {
            // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
            if (d[i] == INF) {
                System.out.println("INFINITY");
            }
            // 도달할 수 있는 경우 거리를 출력
            else {
                System.out.println(d[i]);
            }
        }
    }
}

 

배열로 사용하는법

package personal_project;

import java.util.*;

class Node implements Comparable<Node> {

    private int x;
    private int y;
    private int distance;

    public Node(int x, int y, int distance) {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getDistance() {
        return distance;
    }

    @Override
    public int compareTo(Node other) {
        if (this.distance < other.distance) 
            return -1;
        return 1;
    }
}
class Main {

	public static final int INF = (int) 1e9;
	public static int n, m, start;
	public static int[][] graph = new int[501][501];
	public static int[][] d = new int[501][501];

	public static void dijkstar(int x, int y) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		pq.offer(new Node(x, y, graph[x][y]));
		
		d[x][y] = graph[x][y];

		while (!pq.isEmpty()) {
			Node node = pq.poll();
			int nowDistance = node.getDistance();
            int nowX = node.getX();
            int nowY = node.getY();
			
			int[] dx = {-1,1,0,0};
			int[] dy = {0,0,-1,1};
			
			for(int i=0; i<4; i++) {
				int nx = nowX + dx[i];
				int ny = nowY + dy[i];
				
				if(nx >=0 && ny >= 0 && nx <n && ny < n) {
					int cost = nowDistance + graph[nx][ny];
					if(cost < d[nx][ny]) {
						d[nx][ny] = cost;
						pq.offer(new Node(nx, ny, cost));
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		for (int i = 0; i < n; i++) { 
			for (int j = 0; j < n; j++) { 
				graph[i][j] = sc.nextInt();
				d[i][j] = INF;
			}
		}

		dijkstar(0,0);
		
		System.out.println(d[n-1][n-1]);
	}
}

 

플로이드 워셜 알고리즘

1. '모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해야하는 경우' 사용
2. 다이나믹 프로그래밍이라는 특징이 있다
3. 시간복잡도 : O(N^3)
4. 점화식 : Dab = min(Dab, Dak + Dkb)

import java.util.*;

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M)
    // 노드의 개수는 최대 500개라고 가정
    public static int n, m;
    // 2차원 배열(그래프 표현)를 만들기
    public static int[][] graph = new int[501][501];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 최단 거리 테이블을 모두 무한으로 초기화
        for (int i = 0; i < 501; i++) {
            Arrays.fill(graph[i], INF);
        }

        // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                if (a == b) graph[a][b] = 0;
            }
        }

        // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
        for (int i = 0; i < m; i++) {
            // A에서 B로 가는 비용은 C라고 설정
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = c;
        }

        // 점화식에 따라 플로이드 워셜 알고리즘을 수행
        for (int k = 1; k <= n; k++) {
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                }
            }
        }

        // 수행된 결과를 출력
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
                if (graph[a][b] == INF) {
                    System.out.print("INFINITY ");
                }
                // 도달할 수 있는 경우 거리를 출력
                else {
                    System.out.print(graph[a][b] + " ");
                }
            }
            System.out.println();
        }
    }
}

참고 : 이것이 코딩테스트다 

로직 암기

No	개선된 다익스트라 최단 경로 알고리즘		플로이드 워셜 알고리즘
	class Node(distance, index) INF n, m, start ArrayList graph int[] d	class Node(distance, int x, int y) INF n, m int[][] graph int[][] d	INF n, m int[][] graph = new int[501][501]
1	class Node (distance, index)	class Node (distance, x, y)	for(i<501)
2	INF n, m, start ArrayList graph int[] d	INF n, m int[][] graph int[][] d	무한 초기화 : Arrays.fill(graph[i], INF)
3	dijkstra()	dijkstra()	본인0 초기화 : forforif(a==b) graph[a][b] =0
4	우선순위 큐, 삽입	우선순위 큐, 삽입	그래프 입력 : for(graph[a][b] =c)
5	d[start] =0	d[x][y] = graph[x][y];	graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])
6	while(!pq.isEmpty())	while(!pq.isEmpty())	출력 graph
7	poll	poll	-
8	if(d[now] < dist) continue	dx, dy	-
9	for(size)	for(4방향), 범위	-
10	cost = d[now] + graph.get(now).get(i).getDistance	int cost = nowDistance + graph[nx][ny]	-
11	if(cost < d[graph.get(now).get(i).getIndex])	if(cost < d[nx][ny])	-
12	d[graph.get(now).get(i).getIndex()] = cost	d[nx][ny] = cost	-
13	삽입 : (pq.offer(new Node(graph.get(now).get(i).getIndex(), cost)))	pq.offer(new Node(cost, nx, ny));	-
14	그래프 입력 : graph.get(a).add(new Node(b, c))	그래프 입력 :graph[i][j] = sc.nextInt();	-
15	d배열 무한대 : Arrays.fill(d, INF)	d배열 무한대 : d[i][j] = INF;	-
16	dijkstra(start)	dijkstra(0,0)	-
17	for(d[i])	d[n-1][n-1]	-