약속장소 정하기 (2) - 다익스트라 알고리즘(Dijkstra Algorithm)으로 최단경로 찾기

중간지점이 어디인지 알았으니, 이제 중간지점까지의 최단경로와 거리도 알아야 한다.

 

최단경로와 거리를 구하기 위한 방법에는 여러가지가 있지만, 그중에서 대표적으로 다익스트라 알고리즘을 많이 활용한다.
그 과정을 간단하게 소개하면 아래와 같은데,

 

1. 출발 노드 선택 및 초기화:
- 시작 노드를 선택하고, 다른 모든 노드까지의 최단 거리를 무한대로 초기화
- 시작 노드의 최단 거리는 0으로 초기화

 

2. 현재 노드에서 이웃 노드까지의 거리 계산:
- 현재까지 발견된 최단 거리를 가진 노드를 선택하고, 이 노드에 연결된 모든 이웃 노드까지의 거리를 계산

3. 최단 거리 갱신:
- 계산된 거리가 현재까지 알려진 해당 노드까지의 최단 거리보다 짧으면 해당 노드의 최단 거리를 갱신

 

4. 이웃 노드를 다음으로 선택:
- 최단 거리가 갱신된 노드를 방문한 노드로 선택하고, 아직 방문하지 않은 노드 중에서 최단 거리를 가진 노드를 다음으로 선택

 

5. 모든 노드를 방문할 때까지 반복:
- 위 과정을 모든 노드를 방문할 때까지 반복

 

※ 여기서 노드란 각각의 지점이라고 생각하면 좋을 것 같다.

(이와 관련되어, 링크는 각 노드를 연결한 선 그리고 그래프는 노드와 링크를 나타낸다고 생각하면 좋을 것 같다. 아래 그림 참고)

 

그림출처https://blog.naver.com/PostView.nhn?blogId=sw4r&logNo=222351703995&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

 

 

 

실제 개발을 통해 간단한 예시를 만들어 보겠다.

먼저, 임의로 예시데이터를 만들어보았다. 노드는 초록색 마커 그리고 각 노드별로 연결된 노드들의 링크를 파란색 선으로 표시하였다. 각 노드별로 연결되어있는 노드도 그 노드까지의 거리도 모두 다르게 설정하였다.

 

 

 

이를 graph로 나타내면 아래와 같다.

 

 

이제 한 지점에서 다른 지점까지 최단거리를 구해보자. 예시로 환일종합식품이라는 곳에서 GS25 대림한신점까지의 최단거리와 경로를 구해볼 것 이다.

(실제로는 각 지점 사이에는 수많은 길이 더 있지만, 내가 임의로 지정한 길밖에 길이 없다고 가정했을때 최단경로와 거리를 구해보겠다)

 

 

 

먼저, 우선순위 큐를 나타내는 클래스를 생성한다. 여기서 큐(queue)는 데이터를 저장하는 자료구조중 하나이다.

그리고 이 클래스에 데이터 추가, 데이터 제거, 오름차순 정렬 메서드 등을 만들어 준다.

// 우선순위 큐를 나타내는 클래스
class PriorityQueue {
	
	// 생성자
    constructor() {
        this.queue = [];
    }

    // 큐에 데이터 추가
    enqueue(node, distance) {
        this.queue.push({ node, distance });
        this.sort();
    }

    // 큐에 데이터 제거
    dequeue() {
        return this.queue.shift().node;
    }

    // 비어있을 경우
    isEmpty() {
        return this.queue.length === 0;
    }

    // distance 기준으로 오름차순 정렬
    sort() {
        this.queue.sort((a, b) => a.distance - b.distance);
    }
}

※ sort() : 우선순위 큐에서 가장 작은 distance값을 가진 node가 배열의 앞쪽에 위치하도록 해준다.

 

 

이제 앞에서 설명한 과정을 바탕으로 다익스트라 알고리즘을 통한 최단거리를 구하는 함수를 정의해준다.

(구체적인 내용은 주석 참고)

/**
 * 다익스트라 알고리즘을 사용하여 최단 경로를 찾는 함수
 * @param graph (사용할 그래프)
 * @param start (시작점)
 * @param end	(끝점)
 * @returns 최단거리까지 경로와 최단거리(m)
 */
function dijkstra(graph, start, end) {
	
	// 변수 설정
    const distances = {};										// 거리 배열
    const previous = {};										// 이전에 방문한 노드 배열
    const priorityQueue = new PriorityQueue();					// 큐 생성

    // 출발 노드까지의 거리를 초기화
    for (const node in graph) {
        distances[node] = node === start ? 0 : Infinity;		// node가 시작점이라면 0, 아니면 무한대를 distance[node]에 넣음
        priorityQueue.enqueue(node, distances[node]);			// distances[node]를 우선순위로 node를 추가
        previous[node] = null;									// 이전에 방문한 노드 배열 초기화
    }

    // 본격적인 알고리즘 시작
    while (!priorityQueue.isEmpty()) {
    	
    	// 앞에서 부터 제거해나감
        const current = priorityQueue.dequeue();

        // 최단 경로 찾음
        if (current === end) {
            const path = [];
            let node = end;
            while (node !== null) {
                path.unshift(node);
                node = previous[node];
            }
            
            // 최단 경로를 지도 위에 선으로 표시
            displayShortestPath(path, markers)
            
            return { path, distance: distances[end] };
        }

        // current지점에서부터 다른 노드까지의 거리
        for (const neighbor in graph[current]) {
            
        	// 각각의 거리
        	const newDistance = distances[current] + graph[current][neighbor];

        	// 최단거리 구하기
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                previous[neighbor] = current;
                priorityQueue.enqueue(neighbor, newDistance);
            }
        }
    }

    // 도달할 수 없는 경우
    return { path: null, distance: Infinity };
}

 

(+ 여기에 경로를 빨간선으로 나타내는 함수까지 추가해준다)

 

 

 

dijkstra(graph, " 환일종합식품", " GS25 대림한신점") 함수를 실행해보면

이렇게 시각화 할 수 있고,

 

최단거리는 약 1.85km이고 환일종합식품 -> 코오롱제약 -> 맥스엔영 -> 해태정육점 -> GS25 대림한신점으로 가는 경로가 가장 최단 경로임을 확인할 수 있다.

 

 

이와 유사한 방식으로 실제 길찾기 기능 또는 내비게이션도 만들어질 것이라고 생각한다... (+ 충분한 데이터)