다익스트라 (Dijkstra)

 

 

BFS의 응용으로 "어느 한 정점에서 모든 정점까지의 최단 경로"를  찾는데 사용되며, 매 탐색마다 해당 정점까지의 가중치의 합을 최소값으로 갱신시켜나가는 방식이다.

 

 

 

 

 

 

💡다익스트라 특징

• 가중치 그래프에서 사용되며, 모든 가중치가 음이 아닌 경우에만 적용 한다
  =>음의 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야한다
• 우선순위 큐를 사용하여 현재까지 발견된 최단 거리가 가장 작은 정점을 선택하고, 해당 정점과 인접한 정점들의 최단 거리를 갱신한다
• 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.
• 또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.
• 도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다
• 시간 복잡도는 O(|E|+|V|log|V|)입니다. 여기서 |E|는 간선의 수, |V|는 정점의 수를 나타낸다
  =>선순위 큐를 이용하여 현재까지 발견된 최단 거리가 가장 작은 노드를 선택하기 때문

 

의사코드

1. 출발 노드를 설정한다
2. 최단 거리 테이블을 초기화 한다(출발 노드:0,나머지 :무한대)
3. 우선순위 큐에 출발노드를 넣고 시작한다
4. 우선순위 큐에서 노드를 꺼낸다
5. 해당 노드와 연결된 인접 노드들의 최단 거리를 갱신한다
6. 갱신된 최단 거리를 우선순위 큐에 넣는다
7. 4~6과정을 우선순위 큐가 빌때까지 반복한다

 

📌가중그래프 class

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight });
  }
}

• constructor(): 인접 리스트를 저장할 객체 adjacencyList를 초기화한다
• addVertex(vertex): 주어진 vertex를 인접 리스트에 추가한다 vertex가 인접 리스트에 존재하지 않을 경우, 인접 리스트에 새로운 배열을 추가한다
• addEdge(v1, v2, weight): 두 정점 v1과 v2를 이어주는 가중치가 weight인 간선을 추가한다 v1과 v2 각각의 인접 리스트에 { node: v2, weight }와 { node: v1, weight }를 추가한다

 

📌우선순위 큐

⇒현재까지 발견된 최단 거리가 가장 작은 정점을 선택해야 함

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }
  dequeue() {
    return this.values.shift();
  }
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}​

• constructor(): 우선순위 큐를 저장할 배열 values를 초기화한다
• enqueue(val, priority): 주어진 값 val과 우선순위 priority를 가지는 객체를 values 배열에 추가하고 새로운 원소를 추가할 때마다 sort 메소드를 호출하여 values 배열을 정렬한다
• dequeue(): values 배열의 첫 번째 원소(우선순위가 가장 높은 원소)를 삭제하고 반환한다
• sort(): values 배열을 우선순위에 따라 오름차순으로 정렬한다

 

💡원소를 추가할 때마다 정렬을 수행해야 하므로, 원소가 많은 경우에는 비효율적일 수 있다 

=>  최소 힙을 이용하여 구현하는 방식은 원소를 추가할 때마다 정렬을 수행하지 않아도 되므로 더 효율적(모르니까 우선 넘긴다..)

 

 

📌Dijkstra 알고리즘을 구현

Dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    //가장빨리 갈수 있는 경로 저장
    const previous = {};
    let path = []; //to return at end
    let smallest;
    //초기설정
    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }
//방문할 동안에 반복한다
    while (nodes.values.length) {
//가장 작은 거리를 가지는 노드를 꺼낸다    
      smallest = nodes.dequeue().val;
//정점 끝일 경우 확인하고 빠져나간다
      if (smallest === finish) {
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }
      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjacencyList[smallest]) {
		//각각의 인접점
          let nextNode = this.adjacencyList[smallest][neighbor];
		//우리가 실제 방문 하는 노드가 가지고 있는 거리+인접점에 대한 거리저장
          let candidate = distances[smallest] + nextNode.weight;
		//현재노드의 인접노드 중에서 가장 작은 가중치를 가진 노드
          let nextNeighbor = nextNode.node;
          if (candidate < distances[nextNeighbor]) {
            distances[nextNeighbor] = candidate;
		//경로 최신화
            previous[nextNeighbor] = smallest;
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    return path.concat(smallest).reverse();
  }
}

• 우선순위 큐인 PriorityQueue 클래스를 이용하여 시작점부터 각 노드까지의 거리를 저장한다
• distances 객체에는 시작점에서 각 노드까지의 최단거리가 저장되고, previous 객체에는 해당 노드의 이전 노드가 저장된다
• path 배열은 최종적으로 도착점까지의 최단경로를 저장하기 위한 변수이다
• start와 finish 노드를 받아서 시작점부터 도착점까지의 최단경로를 계산한다
• while 반복문 안에서 우선순위 큐에서 가장 작은 거리를 가지는 노드를 꺼내어 smallest 변수에 저장하고 만약 smallest 변수가 도착점과 같으면, 이전 노드들을 거슬러 올라가며 path 배열에 저장하고 반복문을 빠져나온다
• smallest 변수가 null이거나 distances[smallest]가 Infinity와 같으면 더 이상 처리할 필요가 없으므로, 이전 노드로 돌아간다
• for 반복문에서는 smallest 노드와 인접한 모든 노드에 대해 거리를 계산한다
• 새로운 거리가 더 작은 경우 distances와 previous 객체를 업데이트하고, 우선순위 큐에 해당 노드와 거리를 추가한다
  
• path 배열에는 시작점부터 도착점까지의 최단경로가 역순으로 저장되어 있으므로 concat 함수를 이용하여 smallest 변수를 추가하고, reverse 함수를 이용하여 최종적으로 도착점부터 시작점까지의 최단경로를 반환한다