다익스트라(dijkstra) 알고리즘

개념

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘.

이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로로 모두 찾는다.

동작

인접 행렬로 구현하는 방법

1. 출발 노드와 도착 노드를 설정한다.
2. 최단 거리 테이블을 초기화 한다.
3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 최단 거리 테이블을 갱신한다.
5. 1 ~ 4 과정을 반복한다.

// N: 정점 개수, V: 간선 개수, start: 출발 정점, end: 도착 정점, weight: 비용
// map: 인접 행렬

// 인접 행렬 초기화
for i -> n:
  for j -> n:
    map[i][j] = Integer.MAX_VALUE;

// 가중치 데이터 추가
for i -> V:
  map[start][end] = weight;
  // 무방향 그래프라면
  # map[end][start] = weight;

// dist: 최단 거리 테이블, visited: 방문 노드 확인

// 최단 거리 테이블 초기화
for i -> n:
  dist[i] = Integer.MAX_VALUE;

// 시작 노드 초기화, 출발 노드: v
dist[v] = 0;
visited[v] = true;

// 가중치 정보 추가
for i -> n:
  if visited[i] || map[v][i] == Integer.MAX_VALUE: continue;
  dist[v] = map[v][i];

// dijkstra 구현
for i -> n - 1:
  int min = Integer.MAX_VALUE;
  int idx = -1;

  for j -> n:
    if visited[j] || dist[j] >= min continue;
    min = dist[j];
    idx = j;
  
  if idx == -1 break;
  visited[idx] = true;

  for j -> n:
    if visited[j] || map[idx][j] == Integer.MAX_VALUE || dist[idx] + map[idx][j] >= dist[j]: continue;
    dist[i] = dist[idx] + map[idx][j];

 

우선 순위 큐로 구현하는 방법

1. 출발 노드와 도착 노드를 설정한다.
2. 간선 데이터를 ArrayList [] 로 저장한다.
3. 우선순위 큐를 돌면서 최단 거리를 구한다.

// 간선 정보를 담을 클래스
class Edge implements Comparable<Edge> {
  int e, w;
  Edge (int e, int w) {
    this.e = e;
    this.w = w;
  }

  @Override
  public int compareTo (Edge o) {
    return this.w - o.w;
  }
}
// n: 정점 개수, v: 간선 개수, start: 시작 정점, end: 도착 정점, w: 가중치
// 간선 정보를 저장해둘 ArrayList []
ArrayList<Edge> [] edges = new ArrayList [n + 1];

for i -> v:
  edges[start].add(new Edge(end, w));

// dijkstra 구현
PriorityQueue<Edge> queue = new PriorityQueue<>();
boolean [] visited = new boolean [n + 1];
int [] distance = new int [n + 1];

// 출발 노드: s
queue.offer(new Edge(s, 0));
distance[s] = 0;

while !queue.isEmpty():
  Edge now = queue.poll();

  if (visited[now.end]) continue;

  visited[now.end] = true;
  distance[now.end] = now.w;

  for i -> edges[now.end].size():
    Edge next = edges[now.end].get(i);

    if (visited[next]) continue;

    queue.offer(new Edge(next, now.w + next.w));

특징

다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.

또한 각 단계마다 탐색 노드로 한번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.

도착 노드는 해당노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다.

다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다는 특징이 있다.

 

Tip

정점의 개수가 100000개 이상의 큰 입력이 들어오게 되면 인접행렬 방식으로 풀었을 때 인접행렬의 크기가 100000*100000 개의 2차원 배열이 만들어지게 되어 메모리 초과가 날 수 있다.

 

입력이 인접 행렬로 들어오는 문제가 아닌 이상 우선순위 큐를 사용하여 문제를 해결하자!