[Graph] 다익스트라(Dijkstra) 알고리즘

- 다익스트라

• DP를 활용한 정점과 정점 사이의 최단거리를 알아내는 최단경로알고리즘이다.
  • 하나의 출발지에서 모든 정점을 도착지로 한 최단경로를 구할 수 있다.
• 이때 음의 간선은 포함할 수 없다.
  • Step1. 방문하지 않은 정점 중 S -> 자신으로의 비용이 최소인 정점 선택 
  • Step2. 선택한 정점을 경유지로 해서 아직 방문하지 않은 다른 정점과의 비용을 계산해서 최적을 갱신
  • - 이전에 선택된 정점은 경유지를 통해 가는 것 보다 무조건 더 짧기 때문에 고려 X

• 위 상태에서는 시작점 s(0)를 시작으로 갈 수 있는 정점인 t(10), y(5)을 우선순위 큐에 넣는다.
• 큐는 가중치가 작은 순서대로 정렬므로 y(5)를 기준으로 다시 탐색한다. 이 과정에서 t(10)은 s->y->t(8)의 비용이 더 저렴하므로 t(8), z(7), x(14)로 갱신시켜준다. 
• 그 다음 큐를 poll 하면 가중치가 최소인 z(7)이 선택되고 z와 연결된 정점을 탐색한 후 t -> x를 순서대로 탐색하면 (f)와 같이 시작점 s(0)에서 출발해서 각 정점에 갈 수 있는 최단경로가 저장이 된다.

- 기본적으로 필요한 변수

• PriorityQueue<Node> or Queue<Node> : 정점들을 저장하기 위한 자료구조
  • distance[nr][nc] = Math.min(distance[nr][nc], w + map[nr][nc]);
    pq.add(new Node(nr, nc, distance[nr][nc]));
• map[][], distance[][], check[][](방문체크)
• Class Node(priorityqueue를 위함) / w 가중치가 작은 순으로 저장
  public int compareTo(Node o) {
  return this.w <= o.w ? -1 : 1;
  }

- 문제푸는 팁(오로지 내 생각)

• A->B까지 가는 최단경로를 구하는 문제, 최소비용을 구하는 문제