다익스트라 알고리즘

다익스트라 알고리즘은 그래프의 두 정점 사이에 존재하는 최단 경로를 찾는 것.

다익스트라 알고리즘은 다익스트라 최단 경로 알고리즘의 줄임말이다

그리디 알고리즘의 일종.

다익스트라 알고리즘은 그래프에 대해 작동한다.

코딩을 할때 우선순위 큐를 사용한다

가중치 그래프

정점들을 연결하는 간선에 길이를 나타내는 가중치를 준다

앞에서 보았던 그래프 addEdge 메서드에 가중치를 더해서 객체로 넣는다.

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}); //push하는 값은 객체로 인접하는 정점과 가중치(거리)이다.
        this.adjacencyList[vertex2].push({node:vertex1, weight}); // 정점2도 마찬가지.
    }
}

다익스트라 알고리즘 작동방식

A에서 E로 가는 최단거리를 찾는다.

Previous에는 각 정점에 가장 짧은 경로로 가기 위해 직전에 들려야되는 정점이 들어간다

Visited에는 방문한 정점을 기록.

A에서 출발해서 B와C로 가는 가장 짧은 거리를 찾는다.

그것을 기록하고 B는 4, C는 2이므로 C로 가서 C에서 연결되어 있는 경로 D와 F까지의(A에서시작해서) 거리를 업데이트하고, 그중 가장 짧은 경로를 선택해 간다.

B 4, D 4, F 6이므로 B를 택한다(D를 택해도 괜찮다)

B에 연결된 정점 E, A-E거리는 7이다. 이번엔 E 7, D 4이므로 D로 간다.

D에 연결된 C,E,F중 C는 이미 방문했으므로 E,F중 E 7 이고 F는 그전까진 C를 통해 가면 6이었는데 D를 통해 가면 5이다. 최단거리를 업데이트하고, F로 간다

F에 연결된 CDE중 CD는 이미 방문했고 E로 가는 최단경로가 7이었으나 F에서 가면 6이 된다. 이를 업데이트.

그러면 전부 최단 경로를 찾은 셈이다.

E에서 거꾸로 시작한다. E의 previous F. F의 previous D. 이렇게 최단 경로가 완성된다.

매번 하는 일은 방문하지 않은 노드 중 현재 가장 짧은 거리를 가진 것을 고르는 것.

그리고 그 인접점들을 조사해서 각각에 대해 새로운 최단 거리를 계산한다.

그게 현재 저장된 값보다 작다면 업데이트 → previous도 업데이트

다익스트라 알고리즘 구현

class PriorityQueue { //우선순위 큐는 이진힙을 사용해서 더 성능을 향상시킬 수 있다.
  constructor(){
    this.values = []; //우선순위 큐
  }
  enqueue(val, priority) { //우선순위 큐에 새로운 값을 넣음
    this.values.push({val, priority});
    this.sort(); // 넣고 중요도를 기준으로 정렬
  };
  dequeue() {
    return this.values.shift();
  };
  sort() { // 여기서는 그냥 sort메서드를 쓰지만 이러면 nlogn으로 느리다. 이진 힙을 쓰면 logn 으로 가능하다.
    this.values.sort((a, b) => a.priority - b.priority); // 오름차순. 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){ //시작지점과 도착지점
        const nodes = new PriorityQueue(); // 우선순위 큐를 만든다
        const distances = {}; //최단거리를 저장할 해시테이블, 객체
        const previous = {};  // 최단거리 루트에로 갈때 거쳐야할 이전 정점을 기록
        let path = [] 
        let smallest;
        for(let vertex in this.adjacencyList){
            if(vertex === start){ // 시작점은
                distances[vertex] = 0; // 시작점에서 시작점 까지 거리는 0
                nodes.enqueue(vertex, 0); // 우선순위 큐에 넣음
            } else {
                distances[vertex] = Infinity; //다른 정점들은 일단 무한대로 넣는다
                nodes.enqueue(vertex, Infinity);
            }
            previous[vertex] = null; // 최단경로 previous도 기본값 null로
        }
        while(nodes.values.length){ //우선순위 큐가 비어있지 않으면 계속 루프. 즉 가야할 곳이 남아있다면
            smallest = nodes.dequeue().val; //우선순위 큐 맨 앞에 있는 값. 가장 작은 값. (enqueue할때 sort를 하므로)의 정점만. 맨 처음에는 A가 된다. A는 0, 나머지는 무한대니까.
            if(smallest === finish){ // 만약 우선순위 큐 맨 앞에 있는 값이 도착지라면 끝난것.
                while(previous[smallest]){ //previous에서 이전 정점을 찾아서(A라면 null이므로 루프 끝남)
                    path.push(smallest); // 경로에 넣고
                    smallest = previous[smallest]; //이전 정점을 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; // 다음 지점을 node 이름으로 해주고
                    if(candidate < distances[nextNeighbor]){ // 만약 새 경로의 거리가 distance에 기재된 거리보다 짧으면(즉 최단경로를 새로 발견했다면)
                        distances[nextNeighbor] = candidate; // 새 최단 거리를 업데이트
                        previous[nextNeighbor] = smallest; // 새 최단경로상 previous를 업데이트
                        nodes.enqueue(nextNeighbor, candidate); // 우선순위 큐에 다음 지점과 새 최단거리를 추가한다
                    }
                }
            }
        }
        return path.concat(smallest).reverse();     // path에 모인 경로들을 A와 합친 다음 역순으로
    }
}

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


graph.Dijkstra("A", "E");

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