학습(알고리즘)

다익스트라?알고리즘은 경로들을 순회해 최적경로를 찾을 수 있는 알고리즘이다.

상당히 복잡하지만 길찾기 같은 최적경로 찾는 부분에 상당히 자주 쓸 수 있는 알고리즘이기 때문에 중요한 것 같다.

구조는 아래와 같다.

    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); //nodes에 추가
            }
            previous[vertex] = null; //이전 방문노드도 당연히 null로 초기화
        }
        while(nodes.values.length){ //노드에 값이 남아있는 경우 반복
            smallest = nodes.dequeue().val; //dequeue를 통해 가장 작은 값 제거 및 비교
            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 i = 0 ~ 와 유사)
                    let candidate = distances[smallest] + nextNode.weight;//다음 노드의 값에 간선 가중치를 더하기 
                    let nextNeighbor = nextNode.node;   
                    if(candidate < distances[nextNeighbor]){ //후보지가 현재 최저값보다 낮으면
                        distances[nextNeighbor] = candidate; //최저값을 후보지로 바꾸고
                        previous[nextNeighbor] = smallest; //최저 이전경로를 현재노드(i)로 교체 후
                        nodes.enqueue(nextNeighbor, candidate); //노드에 변경된 최저값을 갱신 
                    }
                }
            }
        }
        return path.concat(smallest).reverse(); //시작점 추가
    }