7주차 : 최단 경로

참조

그래프 이론에 속한다. 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제입니다.

참조

최단 경로 문제의 종류

✔ 단일 출발 최단 경로
: 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제

✔ 단일 도착 최단 경로
: 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제. 그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있습니다.

✔ 단일 쌍 최단 경로
: 모든 정점 쌍들 사이의 최단 경로를 찾는 문제

주요 알고리즘

1. BFS
: 가중치가 없거나 모든 가중치가 동일한 그래프에서 구하는 경우 빠릅니다.

2. 다익스트라 알고리즘
참조
: 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
: 하나의 최단 거리를 구할 떄 그 이전가지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 즉, 현재까지 알고 있던 최단경로를 계속해서 갱신한다.

: 1) 출발 노드 설정 -> 2) 출발 노드 기준 각 노드의 최소 비용 저장 -> 3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 -> 4) 해당 노드 거쳐서 특정한 노드로 가는 경우 고려하여 최소 비용 갱신 -> 5) 위 과정에서 3번 4번을 반복.

참조

// 도착 지점과, 도착 지점으로 가는 비용을 의미하는 클래스
class Node{
	int idx;
    int cost;
    
    Node(int idx, int cost){
    	this.idx = idx;
        this.cost = cost;}
}

public class Dijkstra{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        // 노드와 간선의 개수
        int v = sc.nextInt();
        int e = sc.nextInt();
        // 출발 지점
        int start = sc.nextInt();
        
        // 인접 리스트 이용한 그래프 초기화
        ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
        for(int i=0;i<v+1;i++){
        	graph.add(new ArrayList<>());}
        // 그래프에 값 넣기
        for(int i=0;i<e;i++){
        	int a = sc.nextInt();
            int b = sc.nextIn();
            int cost = sc.nextInt();
            graph.get(a).add(new Node(b,cost));
        }
        
        // 방문 여부를 확인할
        boolean[] visited = new boolean[v+1];
        int[] dist = new int[v+1];
        
        // 최소 거리 정보 담을 배열 초기화
        for(int i=0;i<v+1;i++){
        	// 출발 지점외 나머지 지점까지의 최소 비용은 최대로 지정
            dist[i] = Integer.MAX_VALUE;
        }
        // 출발 지점의 비용은 0으로 시작한다.
        dist[start]=0;
        
        for(int i=0;i<v;i++){
			// 해당 ㅗㄴ드가 가지고 있는 현재 비용
            int nodeValue = Integer.MAX_VALUE;
            // 해당 노드의 인덱스
            int indexIdx=0;
            for(int j=1;j<v+1;j++){
				// 해당 노드를 방문하지 않았고 현재 모든 거리 비용 중 최솟값 찾기
                if(!visited[j] && dist[j]<nodeValue){
                	nodeValue = dist[j];
                    nodeIdx=j;}
                    }
           // 최종 선택된 노드 방문처리    
           visited[nodeIdx]=true;
           
           // 해당 지점 기주능로 인접 노드의 최소 거리값 갱신
           for(int j=0;j<graph.get(nodeIdx).size();j++){
           		// 인접 노드 선택
                Node adjNode= graph.get(nodeIdx).get(j);
                // 인접 노드가 현재 가지는 최소 비용과
                // 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신
                if(dist[adjNode.idx] > dist[nodeIdx]+adjNode.cost){
                	dist[adjNode.idx] = dist[nodeIdx] + adjNode.cost;
                    }
                    }
                    }
     // 5. 최종 비용을 출력한다.
		for (int i = 1; i < V + 1; i++) {
			if (dist[i] == Integer.MAX_VALUE) {
				System.out.println("INF");
			} else {
				System.out.println(dist[i]);
			}
		}
		sc.close();
	}
}

참조
큐를 사용하는 방법은 아래와 같습니다.

class Node implemets Comparable<Node>{
	private int weight;
    private int index;
    
    public Node(int weight, int index){
    	this.weight = weight;
        this.index = index;}
    @Override
    public int compareTo(Node node){
    	return Integer.compare(this.weight, node.weight):
        }
}

// 노드까지의 거리를 저장할 우선순위 큐
// 우선순위 큐 : 순서에 상관없이 우선순위 높은 데이터가 나오는
PriorityQueue<Node> que = new PriorityQueue<>();
// 시작 노드 값 초기화
que.add(new Node(v,0));

// 연결 노드 distance 갱신
for(int i=0;i<n;i++){
	if(!check[i] && maps[v][i] != Integer.MAX_VALUE){
    	distance[i] = maps[v][i];
        que.add(new Node(maps[v][i], i));
        }
}

// 큐가 빌 떄까지 큐에서 노드를 꺼내며 최소 비용 구해가기
while(!que.isEmpty()){
	int min = Integer.MAX_VALUE;
    int min_index = -1;
    
    // 노드 최소값 꺼내기
    Node node= que.poll();
    min =node.weight;
    min_index= node.index;
    
    // 다른 노드를 거쳐서 가는 것이 더 비용이 적은지 확인
    check[min_index]=true;
    for(int i=0;i<n;i++){
    	if(!check[i] && maps[min_index][i] != Integer.MAX_VALUE){
        	if(distance[min_index] + maps[min_index][i] < distance[i]){
            	distance[i] = distance[min_index] + maps[min_index][i];
                que.add(new Node(distance[i], i));
                }
                }
                }
                }

3. 벨만-포드 알고리즘
: 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
: 음수 가중치가 있을 때도 적용할 수 있다.

4. 플로이드-워셜 알고리즘
: 전체 쌍 최단 경로 문제
: 음수 사이클만 존재하지 않으면 음의 가중치를 갖는 간선이 존재해도 상관이 없다.