패스트캠퍼스 챌린지 14일차

최단 경로 알고리즘

 - 두 노드를 잇는 가장 짧은 경로를 찾는 문제

 - 가중치 그래프에서 간선의 가중치 합이 최소가 되도락하는 경로를 찾는 것이 목적

 

 다익스트라 알고리즘

 - 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제

 - 우선순위 큐를 사용하는 방식으로 설명, MinHeap방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보 추출

 

 

 

 

 구현 방법

 1) 첫 정점을 기준 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장

  - 초기에는 첫 정점의 거리 0, 나머지는 무한대(inf)로 저장

 

 2) 우선순위 큐에서 노드를 꺼냄

   - 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내진다.

   - 첫 정점에 인접한 노드를 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서

     각 정점까지의 거리를 비교한다

   - 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해동 노드의 거리를

     업데이트 한다.

   - 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.

     => 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 된다.

     ※ 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리를 가진 경우에는 해당 노드와 인접한 

        노드간의 거리를 계산하지 않는다. 

 

 3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을떄 까지 반복한다.

 

다익스트라 알고리즘 구현

 

 1) Edge를 나타내는 Edge class

public class Edge implements Comparable<Edge> {
    public int distance;
    public String vertex;
    
    public Edge(int distance, String vertex) {
        this.distance = distance;
        this.vertex = vertex;
    }
    
    // System.out.println() 으로 객체 자체 출력시, 
    public String toString() {
        return "vertex: " + this.vertex + ", distance: " + this.distance;
    }
    
    @Override
    public int compareTo(Edge edge) {
        return this.distance - edge.distance;
    }
}

 

 2) 자바의 우선순위 큐 객체인 PriorityQueue 클래스를 사용하여 구현

import java.util.PriorityQueue;
import java.util.HashMap;

public class DijkstraPath {
    public HashMap<String, Integer> dijkstraFunc(HashMap<String, ArrayList<Edge>> graph, String start) {
        HashMap<String, Integer> distances = new HashMap<String, Integer>();
        for (String key : graph.keySet()) {
            distances.put(key, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
        priorityQueue.add(new Edge(distances.get(start), start));
        
        // 알고리즘 작성
        return distances;
    }
}

 

다익스트라 구현

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

public class DijkstraPath {
    public HashMap<String, Integer> dijkstraFunc(HashMap<String, ArrayList<Edge>> graph, String start) {
        Edge edgeNode, adjacentNode;
        ArrayList<Edge> nodeList;
        int currentDistance, weight, distance;
        String currentNode, adjacent;
        HashMap<String, Integer> distances = new HashMap<String, Integer>();
        for (String key : graph.keySet()) {
            distances.put(key, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
        priorityQueue.add(new Edge(distances.get(start), start));
        
        // 알고리즘 작성
        while (priorityQueue.size() > 0) {
            edgeNode = priorityQueue.poll();
            currentDistance = edgeNode.distance;
            currentNode = edgeNode.vertex;
            
            if (distances.get(currentNode) < currentDistance) {
                continue;
            }
            
            nodeList = graph.get(currentNode);
            for (int index = 0; index < nodeList.size(); index++) {
                adjacentNode = nodeList.get(index);
                adjacent = adjacentNode.vertex;
                weight = adjacentNode.distance;
                distance = currentDistance + weight;
                
                if (distance < distances.get(adjacent)) {
                    distances.put(adjacent, distance);
                    priorityQueue.add(new Edge(distance, adjacent));
                }
            }
        }
        return distances;
    }
}

 

다익스트라 알고리즘 실행

HashMap<String, ArrayList<Edge>> graph = new HashMap<String, ArrayList<Edge>>();
graph.put("A", new ArrayList<Edge>(Arrays.asList(new Edge(8, "B"), new Edge(1, "C"), new Edge(2, "D"))));
graph.put("B", new ArrayList<Edge>());
graph.put("C", new ArrayList<Edge>(Arrays.asList(new Edge(5, "B"), new Edge(2, "D"))));
graph.put("D", new ArrayList<Edge>(Arrays.asList(new Edge(3, "E"), new Edge(5, "F"))));
graph.put("E", new ArrayList<Edge>(Arrays.asList(new Edge(1, "F"))));
graph.put("F", new ArrayList<Edge>(Arrays.asList(new Edge(5, "A"))));


// 실행
DijkstraPath dObject = new DijkstraPath();
dObject.dijkstraFunc(graph, "A");

 

시간 복잡도

 - 과정 1 : 각 노드는 최대 한 번씩 방문하므로 그래프의 모든 간선은 최대 한 번씩 검사 시간복잡도 : O(E)

 - 과정 2 : 우선순위 큐에 가장 많은 노드 ,거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 떄마다,

   배열의 최단거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는것이며 추가되는 각 간선마다 최대 한 번

   일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은

   시간복잡도 : O(ElogE)가 걸린다

   총 시간복잡도 : O(E) + O(logE) = O(ElogE)

 

14일차 인증

 

 

개념은 어느정도 이해가 가지만 코드는 다시봐도 이해가 완벽하게 가지 않는다 다시 한번 강의를 듣는 것도 좋을듯..

아니면 다른 예제를 보고 좀 더 이해하는것이 좋을듯 하다.

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]