최단 경로 찾기 (Dijkstra)

다익스트라 알고리즘

1. 출발점이 있다.
2. 다른 모든 도시로의 최소 시간을 구할 수 있다.
3. 3개 중 가장 빠름
4. O(ElogV)

원리

• Priority Queue를 이용

1. 모든 정점까지의 거리를 무한대로 초기화
2. 출발점에서 방문할 수 있는 정점과 거리를 Queue에 넣기
3. Queue에서 꺼낸다.
4. 꺼낸 정점까지의 거리값과 기존에 가지고 있는 그 정점까지의 최단 거리와 비교
5. 최단거리가 갱신되는 경우 갱신하고 Queue에 넣기
6. 한 정점에 대해 최단거리를 먼저 방문하게 되는데 방문했던 정점의 경우 패스 또는 지금까지 이 정점에 방문한 거리가 살펴볼 거리보다 적으면 패스

구현

class Node implements Comparable<Node> {
    int dest;
    int cost;
    
    @Override
    public int compareTo(Node o) {
    	return this.cost - o.cost;
    }
}

void dijkstra(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<Node>();
    
    cost[start] = 0;
    pq.offer(new Node(start, 0));
    
    while(!pq.isEmpty()) {
    	Node now = pq.poll();
        
        if(cost[now.dest] < now.cost) continue;
        // 지금까지 계산된 현재 정점까지의 거리가 더 작은 경우 패스
        
        for(Node next : adjList[now.dest]) {
            if(cost[next.dest] > next.cost + now.cost) {
                // 현재 정점을 거쳐가는 것이 더 낫다면
                cost[next.dest] = next.cost + now.cost;
                pq.offer(new Node(next.dest, cost[next.dest]);
            }
        }
    }
}

플로이드-워셜 알고리즘

1. 모든 도시 간 최소 시간을 구할 수 있다.
2. 출발점이 없어도 된다.
3. 3개 중 가장 느림
4. O(V^3)

벨만포드 알고리즘

1. 걸리는 시간이 음수인 경우가 있다.
2. 출발점이 있다.
3. 다른 모든 도시로의 최소 시간을 구할 수 있다.
4. O(VE)