최단 경로 알고리즘

최단 경로 알고리즘

정점으로부터 정점까지의 모든 경로 중에서 가장 비용이 작은 경로

 

(1) Dijkstra

(정점을 고르는 정점 중심)

• 출발 정점으로부터 다른 모든 정점까지의 거리를 선택된 정점을 지나서 가는 경우와 직접 가는 경우 중 최솟값을 갱신해가면서 가장 가까운 정점을 하나씩 선택된 정점에 편입시켜가며 최단 경로를 갱신
• 음의 가중치를 허용하지 않음

기능	특징	시간 복잡도(노드 수 : V, 에지 수 : E)
출발 노드와 모든 노드간의 최단 거리 탐색	에지는 모두 양수	O(ElogV)

public class Dijkstra_Test {
 
    static class Edge implements Comparable<Edge> {
        int v, weight;
 
        public Edge(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());    // 정점의 개수
        int E = Integer.parseInt(st.nextToken());    // 간선의 개수
        int K = Integer.parseInt(br.readLine()) - 1;    // 시작 정점(번호를 1부터 input)
        final int INF = Integer.MAX_VALUE;
        
        // 인접 리스트 준비
        List<Edge>[] adj = new ArrayList[V];
        for (int i = 0; i < V; i++) 
            adj[i] = new ArrayList<>();
        
        // 간선 정보 입력
        for (int i = 0; i < E; i++)  {
            st = new StringTokenizer(br.readLine());
            adj[Integer.parseInt(st.nextToken()) - 1].add(new Edge(Integer.parseInt(st.nextToken()) - 1, 
                    Integer.parseInt(st.nextToken())));
        }
    
        // dist 배열
        int[] dist = new int[V];
        boolean[] checked = new boolean[V];
        
        // dist 배열을 INF로 초기화
        Arrays.fill(dist, INF);
        // 시작점은 0으로 변경
        dist[K] = 0;
        
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.add(new Edge(K, 0));
        Edge cur = null;
        
        while(!pQ.isEmpty()) {
            // check되지 않았으면서,
            // 현재(i)정점으로부터 dist 값이 제일 작은 정점(j)의 번호 찾기
            cur = pQ.poll();
            if(checked[cur.v]) continue;
            
            // 찾은 정점(j)으로부터 갈 수 있는 경로가 이미 알고 있는 dist보다 작다면 갱신
            // index가 가지고 있는 모든 간선을 검사
            for (Edge next : adj[cur.v]) {
                // check되지 않았으면서 다음 노드 까지의 거리가
                // 나까지 거리 + 나로부터 다음 노드까지 거리보다 작다면 갱신 
                if(!checked[next.v] && dist[next.v] > dist[cur.v] + next.weight) {
                    dist[next.v] = dist[cur.v] + next.weight;
                    pQ.add(new Edge(next.v, dist[next.v]));
                }
            }
            
            // 체크 완료
            checked[cur.v] = true;
        }
        
        for (int i = 0; i < V; i++) {
            if(dist[i] == INF) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }
}

 

 

(2) Bellman-Ford

(간선을 고르는 간선 중심)

(n-1)번 반복하기

기능	특징	시간 복잡도(노드수 : V, 에지 수 : E)
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색	- 음수 가중치 에지가 있어도 수행할 수 있음 - 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음	O(VE)

 

 

Floyd-Warshall

기능	특징	시간 복잡도(노드 수 : V)
모든 노드 간에 최단 경로 탐색	- 음수 가중치 에지가 있어도 수행할 수 있음 - 동적 게획법의 원리를 이용해 알고리즘에 접근	O(V^3)

 

[도출한 플로이드-워셜 점화식]

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

public class FloydWarshall_Test {
 
    static final int INF = 987654321;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        int[][] adjMatrix = new int[N][N];
 
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                adjMatrix[i][j] = sc.nextInt();
                // 자기자신으로의 인접 정보가 아니고 인접해있지 않다면 INF로 채우기
                if (i != j && adjMatrix[i][j] == 0) {
                    adjMatrix[i][j] = INF;
                }
            }
        }
 
        // 경유지 -> 출발지 -> 도착지
        for (int k = 0; k < N; ++k) {
            for (int s = 0; s < N; ++s) {
                // 출발지와 경유지가 같다면 pass
                if (s == k) continue; 
                
                for (int e = 0; e < N; ++e) {
                    // 경유지와 목적지가 같거나 출발지가 곧 목적지라면 pass
                    if (s == e || k == e) continue; 
                    
                    // 경유한 길이 최단 거리라면 갱신
                    if (adjMatrix[s][k] + adjMatrix[k][e] < adjMatrix[s][e]) 
                        adjMatrix[s][e] = adjMatrix[s][k] + adjMatrix[k][e];
                }
            }
            for(int i=0; i<N; ++i) {
                for(int j=0; j<N; ++j) {
                    System.out.print(adjMatrix[i][j]+"\t");
                }
                System.out.println();
            }
            System.out.println("=====================================");
    
        }
 
    }
 
}