알고리즘, graph, Dijkstra

 

다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 가중치가 음수가 아닌 경우에만 적용할 수 있습니다.

다익스트라 알고리즘의 개념

1. 시작 정점 선택: 알고리즘은 시작 정점에서 시작합니다.
2. 최단 경로 집합: 최단 경로를 확정한 정점들의 집합을 유지합니다.
3. 미확정 집합: 아직 최단 경로가 확정되지 않은 정점들의 집합을 유지합니다.
4. 거리 배열: 시작 정점에서 각 정점까지의 현재까지 발견된 최단 거리를 저장합니다. 초기에는 시작 정점의 거리를 0으로 설정하고 나머지 정점의 거리를 무한대로 설정합니다.
5. 이웃 정점 업데이트: 현재 정점에서 인접한 정점들로의 거리를 계산하고, 더 짧은 경로를 발견하면 거리를 업데이트합니다.
6. 반복: 모든 정점의 최단 경로가 확정될 때까지 이 과정을 반복합니다.

다익스트라 알고리즘의 과정

출처 [https://cs.slides.com/colt_steele/graphs#/115]

 

 

1. 시작 정점을 설정하고, 시작 정점의 거리를 0으로 설정합니다.
2. 현재 정점에서 인접한 모든 정점의 거리를 업데이트합니다.
3. 아직 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택하여, 그 정점으로 이동합니다.
4. 이 과정을 모든 정점이 방문될 때까지 반복합니다.

다익트라 메서드의 의사코드

• 이 함수는 시작 정점과 끝 정점을 받아야 합니다.
• 객체(이를 distances라고 부르겠습니다)를 만들고 각 키를 인접 리스트의 모든 정점으로 설정하되, 시작 정점은 0의 값을 가지도록 하고 나머지는 무한대의 값을 가지도록 합니다.
• distances 객체에 값을 설정한 후, 시작 정점을 제외한 각 정점을 우선순위 큐에 무한대의 우선순위로 추가합니다. 시작 정점은 우리가 시작하는 곳이므로 우선순위가 0이어야 합니다.
• previous라는 또 다른 객체를 만들고 각 키를 인접 리스트의 모든 정점으로 설정하되, 값은 null로 설정합니다.
• 우선순위 큐에 항목이 있는 동안 반복을 시작합니다.
  • 우선순위 큐에서 정점을 dequeue합니다.
  • 해당 정점이 끝 정점과 같으면 - 완료입니다!
  • 그렇지 않으면 해당 정점의 인접 리스트의 각 값을 반복합니다.
    • 시작 정점에서 해당 정점까지의 거리를 계산합니다.
    • 그 거리가 현재 distances 객체에 저장된 값보다 작으면
      • distances 객체를 새로운 더 짧은 거리로 업데이트합니다.
      • previous 객체에 해당 정점을 포함하도록 업데이트합니다.
      • 시작 노드로부터의 총 거리로 정점을 큐에 enqueue합니다.

자바스크립트로 다익스트라 알고리즘 구현

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);
  }
}

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }
  Dijkstra(start, finish) {
    // nodes dequeue 할 때, 가중치가 낮은 것을 먼저 뽑아 순회하기 위한 우선순위 큐 클래스
    const nodes = new PriorityQueue();
    // distances - 시작 정점을 기준으로 가장 짧은 거리를 저장해두는 객체
    const distances = {};
    // previous - 최종적으로 최단거리를 기억할 수 있는 객체
    const previous = {};
    // target - 우리가 실제로 방문하는 노드
    let target;
    // path - 최단 거리를 저장해서 반환할 배열
    let path = [];

    //build up initial state
    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;
    }

    console.log('nodes.values:', nodes.values);
    console.log('distances:', distances);
    console.log('previous:', previous);
    console.log('adjacencyList:', this.adjacencyList);
    // as long as there is something to visit
    while (nodes.values.length) {
      target = nodes.dequeue().val;
      if (target === finish) {
        //WE ARE DONE
        //BUILD UP PATH TO RETURN AT END
        while (previous[target]) {
          path.push(target);
          target = previous[target];
        }
        break;
      }
      if (target || distances[target] !== Infinity) {
        for (let neighbor in this.adjacencyList[target]) {
          //find neighboring node
          let nextNode = this.adjacencyList[target][neighbor];
          //calculate new distance to neighboring node
          let newDistance = distances[target] + nextNode.weight;

          console.log('nextNode:', nextNode);
          console.log('newDistance:', newDistance);

          if (newDistance < distances[nextNode.node]) {
            //updating new target distance to neighbor
            distances[nextNode.node] = newDistance;
            //updating previous - How we got to neighbor
            previous[nextNode.node] = target;
            //enqueue in priority queue with new priority
            nodes.enqueue(nextNode.node, newDistance);
          }
        }
      }
    }
    return path.concat(target).reverse();
  }
}

var graph = new WeightedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);

console.log(graph.Dijkstra('A', 'E'));

// ["A", "C", "D", "F", "E"]

다익스트라 알고리즘의 시간 복잡도

• 우선순위 큐를 사용하지 않은 경우: (O(V^2))
• 우선순위 큐를 사용한 경우 (예: 힙 사용):
  • 삽입/삭제: (O(log V))
  • 총 시간 복잡도: (O((V + E) log V))

다익스트라 알고리즘의 특징

1. 단일 시작점: 시작 정점에서 다른 모든 정점으로의 최단 경로를 구합니다.
2. 비음수 가중치: 간선의 가중치가 음수인 경우에는 사용할 수 없습니다.
3. 효율성: 우선순위 큐(힙)를 사용하면 큰 그래프에서도 비교적 효율적으로 작동합니다.

다익스트라 알고리즘은 네트워크 라우팅, 지도 서비스, 교통 시스템 등 다양한 분야에서 널리 사용됩니다.