[최단경로] 다익스트라 알고리즘 Dijkstra Algorithm

http://devdasom.tistory.com/86

다익스트라 알고리즘은 음수 가중치를 갖지 않는 방향이 있는 그래프에서 출발점과 도착점 사이의 최단 경로를 알아내는 알고리즘.

우선순위 큐를 사용하여 현재 가장 짧은 거리를 가진 정점을 찾아 다음 방문 정점으로 선택한다.

package path.bj1753;

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * Created by dasom on 2016-10-18.
 */
public class DijkstraAlgorithm {
    public static final int INF = 10000000;

    public static void main(String[] args) throws IOException {
        
        //BufferedReader와 StringTokenizer 사용하여 읽어오는 방법. --> 이게 훨씬 빠르다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int nVertex = Integer.parseInt(st.nextToken());
        int nEdge = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine()) - 1;

        Vector<Element>[] adj = new Vector[nVertex];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Vector<>();
        }

        for (int i = 0; i < nEdge; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            adj[start - 1].add(new Element(weight, end - 1));
        }

        int[] dist = new int[nVertex];
        boolean[] visited = new boolean[nVertex];

        for (int i = 0; i < nVertex; i++) {
            dist[i] = INF;
            visited[i] = false;
        }

        PriorityQueue<Element> pq = new PriorityQueue<>();

        //--start Dijkstra Algorithm
        dist[K] = 0;    //시작점에서 시작점까지의 거리는 0이므로 초기화해준다.
        pq.offer(new Element(0, K));

        while (!pq.isEmpty()) {
            int curVertex;
            do {
                curVertex = pq.peek().vertex;
                pq.poll();
            } while (!pq.isEmpty() && visited[curVertex]);

            if (visited[curVertex]) break;

            for (Element e : adj[curVertex]) {
                int next = e.vertex;
                int oldDis = dist[next];
                int newDis = dist[curVertex] + e.dis;

                if (newDis < oldDis) {
                    dist[next] = newDis;
                    pq.offer(new Element(newDis, next));
                }
            }
        }
        //--end of Dijkstra Algorithm

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < dist.length; i++) {
            if (dist[i] == INF) sb.append("INF").append("\n");
            else sb.append(dist[i]).append("\n");
        }

        System.out.println(sb.toString().trim());
    }
}

class Element implements Comparable<Element> {
    int dis;
    int vertex;

    public Element(int dis, int vertex) {
        this.dis = dis;
        this.vertex = vertex;
    }


    @Override
    public int compareTo(Element o) {
        return dis <= o.dis ? -1 : 1;
    }
}

백준 온라인 저지

1753번 최단경로

백준 온라인 저지의 1753번 문제(최단경로)의 입력값을 넣어 얻은 출력결과입니다.

입력

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력

0
2
3
7
INF