hyeoneee's blog

어떤 정점에서 출발해서 모든 노드들로 가기까지 최단거리들을 구하는 알고리즘

특징

1. 음의 가중치가 없다. 무조건 양의 가중치이다.

-> 가중치가 모두 같으면? BFS로푼다.

2. 이전에 풀었던 부분 최단거리가 최단거리임을 보장한다.

3. Priority Queue를 사용하여 가중치순으로 정렬한다.

Priority Queue<Node> pq = new Priority Queue <>( (o1,o2)->Long.compare(o1.cost,o2.cost);

pq를 사용하는 이유?

• Cost순으로 정렬되기 위해, 거리가 적은 순으로 뽑아서 그 노드를 거쳐서 가면
• 최소임이 보장되기 때문에 pq를 사용한다.

4. 최단거리 배열은 MAX값으로 초기화 시켜준다 ( 최단거리를 구하기 위해)

5. 인접배열은 양방향, 단방향을 고려해준다.

응용

1. 왔다 갔다 최단거리 (출발 -> 도착 정점 -> 출발)

-  출발정점에서 최단거리 구하고 도착정점에서 최단거리 더해서 두개 더해

2. 단일 도착 지점에 대한 최단거리 (1~N-1 번 정점에서 출발 N번 도착)

- 반대로 N에서 출발해서 최단거리 구하기

3. 여러 지점에서 출발하는 최단거리

- 가상의 출발지점에서 가중치 0으로 출발 지점들을 연결한 후 최단거리 구하기

4. 최단거리의 경우의 수 구하기 ( 백준 14554 )

 - 배열하나를 더 선언해, 최단거리로 업데이트 하면, 다음 경로로 가는 경우의 수에 기존 경로의 수를 넣어주고,

   최단거리가 같으면? 해당 지점에 오는 경우의수가 늘어나는 것이므로, 

   다음 경로의 수에 기존경로+ 다음경로를 더해준다.

                        if (dist[newX][newY] > dist[now.x][now.y] + cost) { // 최단거리 업데이트
                            dist[newX][newY] = dist[now.x][now.y] + cost;
                            pq.add(new Node(newX, newY, dist[newX][newY], 0));
                            path[newX][newY] = path[now.x][now.y];
                        } else if (dist[newX][newY] == dist[now.x][now.y] + cost) { // 최단거리가 같으면
                            path[newX][newY] = path[now.x][now.y] + path[newX][newY]; // 경우의수 누적
                        }

샘플 코드

    static int[] dist;
    static int N;
    static PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1.cost,o2.cost));
    static ArrayList<Node>[] adj = new ArrayList[N+1]; // main에서 초기화 필요 
	static void dijkstra() {
        //0. 초기화 dist 배열 INF 값으로 채우기 , 시작점은 0, q에 시작점 add
        Arrays.fill(dist, INF);
        dist[1] = 0;
        pq.add(new Node2(1, 0));

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (dist[now.idx] < now.cost) { // 현재 노드의 최소거리가 가져온 cost 보다 작다면 넘어가도됨
                continue; // 이미 최단거리를 확정했으면 돌필요가없음 아니면 시간초과
            }
            for (Node next : adj[now.idx]) {
                if (dist[next.idx] > dist[now.idx] + next.cost) { // 최단거리이면
                    dist[next.idx] = dist[now.idx] + next.cost; // 거리 업데이트 해주고
                    pq.add(new Node(next.idx, dist[next.idx]); // pq에 값 넣기 -> cost : 업데이트된 거리값
                }
            }
        }
    }

알고리즘 시험에 패스한 기념으로

그동안 알고리즘 공부한걸 정리해보고자 한다 ^^ (기쁜맘으로)

그렇담 우선 Graph 최단거리 3종 아이들부터 정리해보고자 한다.

최단거리 알고리즘은 3가지가 대표적이다.

1. 다익스트라

2. 벨만포드

3. 플로이드 워셜

1) 시작점 , 도착점

1 to 1 : 다익스트라

1 to N : 다익스트라

N to 1 : 다익스트라 (역방향 그래프를 만들어 도착점을 출발점으로 하는 1 to N 다읷트라 수행) - 역다익

N to N : 플로이드 워셜

2) 간선의 가중치

가중치가 없으면?   BFS

가중치가 있으면서 양수이면 ? 다익스트라 (=> Priority Queue 사용)

가중치가 있으면서, 음수이면? 벨만포드 

3) 트리 

-> LCA