다익스트라

최단 경로

그래프가 있다
버텍스(정점)와 엣지(간선)가 있고 엣지에는 가중치가 있다
이때 특정 버텍스와 버텍스간에 엣지의 가중치 합이 최소가 되는 경로를 찾는 알고리즘이다.

문제의 종류

1단일출발 최단경로 문제
특정 노드에서 출발하여 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제
2단일 도착 최단 경로 문제
모든 노드에서 출발해서 그래프 내의 특정 노드로 도착하는 가장 짧은 경로를 찾는문제
3단일 쌍 최단 경로 문제
주어진 노드 U와 V간 최단 경로 찾는 문제
4전체 쌍 최단 경로
그래프 내의 모든 노드 쌍 사이에 대한 최단 경로를 찾는 문제

다익스트라 알고리즘

하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 알고리즘이다
위의 문제의 종류에서 1번에 해당한다.

A 버텍스에서 B, D, C, E로 갈 수 있는 최단 거리는 얼마일까
B5, C4, D3, E6 이다 이런 결과를 도출하는것이 다익스트라이다
다익스트라는 BFS 와 유사하다

1)다익스트라에는 배열이 필요하다 이 배열에 A와 ABCDEF 각 정점 사이의 거리를 저장하고 탐색과정에서 계속 갱신한다. A는 0 나머지는 최대값을 넣는다
다익스트라에는 최소힙자료구조가 필요해서 우선순위큐도 사용한다.PrioirtyQueue 컬렉션을 사용하면 된다.
PQ 에 첫정점과 거리0을 넣는다.

minHeap.add(new Edge(start, 0));

2)PQ 에서 Edge을 꺼낸다. Edge의 버텍스와 인접한 간선의 가중치와 배열의 가중치를 비교하고 인접한 간선의 가중치가 더 작으면 배열을 갱신한다. 갱신하는 경우 PQ에 넣는다
BFS와 유사하게 인접한 정점들을 순차적으로 탐색한다. 2번과정을 PQ가 비어있는 상태가 될때까지 반복한다

public class Dijkstra {

    private class Edge implements Comparable<Edge>
    {
        public Integer distance;
        public String vertex;

        Edge(String vertex, Integer distance)
        {
            this.distance = distance;
            this.vertex = vertex;
        }

        @Override
        public int compareTo(@NotNull Edge o) {
            return this.distance - o.distance;
        }
    }

    HashMap<String, Integer> find(HashMap<String, HashMap<String, Integer>> graph, String start)
    {
        PriorityQueue<Edge> meanHeap = new PriorityQueue<>();
        HashMap<String, Integer> length = new HashMap<>();

        meanHeap.add(new Edge(start, 0));
        for(String key : graph.keySet())
        {
            length.put(key, Integer.MAX_VALUE);
        }
        length.put("A", 0);

        while(meanHeap.isEmpty() == false)
        {
            String cur = meanHeap.poll().vertex;
            HashMap<String, Integer> adjV = graph.get(cur);

            for(String key : adjV.keySet())
            {
                Integer dis = adjV.get(key)+length.get(cur);
                if(length.get(key) > dis)
                {
                    length.put(key, dis);
                    meanHeap.add(new Edge(key, dis));
                }
            }
        }

        return length;
    }
}

public class DijkstraTest {

    public static void main(String[] args) {

        Dijkstra dijk = new Dijkstra();

        HashMap<String, HashMap<String, Integer>> graph = new HashMap<>();
        HashMap<String, Integer> adjA = new HashMap<>();
        adjA.put("B", 8);
        adjA.put("C", 1);
        adjA.put("D", 2);
        graph.put("A", adjA);

        graph.put("B", new HashMap<>());

        HashMap<String, Integer> adjC = new HashMap<>();
        adjC.put("B", 5);
        adjC.put("D", 2);
        graph.put("C", adjC);

        HashMap<String, Integer> adjD = new HashMap<>();
        adjD.put("E", 3);
        adjD.put("F", 5);
        graph.put("D", adjD);

        HashMap<String, Integer> adjE = new HashMap<>();
        adjE.put("F", 1);
        graph.put("E", adjE);

        HashMap<String, Integer> adjF= new HashMap<>();
        adjF.put("A", 5);
        graph.put("F", adjF);

        HashMap<String, Integer> result = dijk.find(graph, "A");

        for(String key : result.keySet())
        {
            System.out.println("Key: " + key + ", dis: " + result.get(key));
        }
    }


}