최소경로

오랜만에 알고리즘을 잡으니 최소경로와 최소신장이 헷갈리고 기억도 잘 안나서 정리를 해본다.

# 용어

최소경로

 

• 가중치가 없다
  • bfs
    • 가장 먼저 도착하는게 최단
    • 도착하자마자 끝내면 된다
• 가중치가 있다(완탐)
  • 하나의 시작 정점에서 끝 정점까지의 최단 경로
    • 다익스트라(dijkstra)
      • 음의 가중치 허용x
    • 벨만 포드(Bellman-Ford)
      • 음의 가중치 허용
  • 모든 정점들에 대한 최단 경로
    • 플로이드-워샬(Floyd-Warshall)
      • 따지고보면 다익스트라를 N만큼 반복해줘도 된다
      • 실제로 시간복잡도도비슷하게 나옴

다익스트라Dijkstra

방식

• 그리디하게 진행된다.
• 시작점으로부터 가장 저비용인 곳을 선택하면서 최단 경로를 알아낸다.
• 그리디하게 해결 가능한 이유
  • 음의 가중치가 없는 경우에 한하기 때문
     

 

배열 사용

map을 사용

boolean[] visited; // 방문배열
int[] distance; //거리배열

// 초기화
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;

for(N회반복) {
    min = Integer.MAX_VALUE;
    for(j=0~N){
      // 첫 반복에서 방문x+min보다 적은 비용은 distance[start]가 유일하다.
      if(!visited[j] && min > distance[j]) { 
          min = distance[j];
          now = j;
      }
    }
    visited[now] = true;
    // 기존비용vs경유비용
    for(j=0~N) {
      if(!visited[j] 
          && map[now][j]!=Integer.MAX_VALUE 
          && distance[j] > min+map[now][j]) {
          distance[j] = min+map[now][j]
      }
    }
}

 

 

PriorityQueue 사용

graph를 사용
시작위치로 부터 모든 지점까지의 최단거리를 구하고 distance[end]를 출력

static class Node implements Comparable<Node> {
    int end, cost;
    ...
}

...

// 도시간 비용을 그래프로 나타냄
ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
for (int i = 0; i < N; i++) {  // 초기화
    graph.add(new ArrayList<Node>());
}
for (int i = 0; i < N; i++) {  // 입력받으면서 비용기록
    ...
    graph.get(start).add(new Node(end, cost));
}

// 초기화
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;

// pq
PriorityQueue<Node> q = new PriorityQueue();
q.offer(new Node(start, 0));

// 최단거리 탐색
while(!q.isEmpty()){
    Node now = q.poll();

    // 시작점에서 현재도시로의 비용보다 > 시작점에서 다음 도시로의 비용이 적으면 continue
    if(distance[now.end] < now.cost) continue;

    // 선택된 노드(pq니까 최저비용 노드)의 인접 노드 확인
    for (int i = 0; i < graph.get(now.end).size(); i++) {
        Node next = graph.get(now.end).get(i);
        // 기존비용vs경유비용
        if(distance[next.end] > now.cost+next.cost) {
            distance[next.end] = now.cost+next.cost;
            q.offer(new Node(next.end, distance[next.end]));
        }
    }
}

 

문제

- 백준 1916 최소비용 구하기  https://www.acmicpc.net/problem/1916