그래프 (3) : 가장 짧은 경로

이번 포스팅에서는 가중 그래프와 최단 거리 찾기에 자주 사용되는 알고리즘에 대해 알아보도록 하겠습니다.

 

---

1. 가중 그래프(Weighted graph) 란?

그래프에는 다양한 변형이 존재합니다.
그래프 간선에 정보를 추가하는 가중 그래프 역시 또 하나의 유용한 그래프 유형입니다.

 

 

위 그래프와 같이 간선에 비용, 거리 등을 데이터를 부여하여 사용됩니다.

코드로 구현한다면 아래와 같이 구현할 수 있습니다.

 

class WeightedGraphVertex {
    data;
    // 배열 대신 해시 테이블 사용하여 가중치 삽입
    adjacentVertices;

    constructor(data) {
        this.data = data;
        this.adjacentVertices = new Map()
    }

    addAdjacentVertex(vertex, weight) {
        this.adjacentVertices.set(vertex, weight)
    }
}

 

---

 

2. 데이크스트라의 알고리즘 (Dijkstra algorithm)

 

가중 그래프는 다양한 데이터 셋을 훌륭히 모델링하며 강력한 알고리즘까지 제공합니다.
그중 하나가 바로 데이크스트라 알고리즘이며 최단 경로 문제 (Shortest Path Problem)에 활용 됩니다.
데이크스트라 알고리즘을 수행하면 목적지까지 도달하는 최단 경로뿐만 아니라 시작 지점에서 다른 목적지로 가는 모든 최소비용을 알 수 있게 됩니다.

그렇다면 데이크스트라 알고리즘은 어떻게 수행할까요?

도시간 길 찾기를 예로 들어보겠습니다.
때문에 정점을 "도시"로 묘사하겠습니다.
우선 준비물이 필요합니다.

1. 출발 지점 부터 해당 도시까지의 최소 비용을 저장하는 테이블
2. 출발 지점 부터 해당 도시까지 최소 비용으로 이동하는 경로의 마지막 경유지를 저장하는 테이블

아래가 알고리즘의 단계입니다.

 

1. 시작 도시에 방문해 "현재 도시"로 만듭니다.

2. 현재 도시에서 각 인접 도시로의 비용을 확인합니다.

3. 시작 도시에서 인접 도시로의 비용이 현재 저장된 인접 도시로의 최소 이동 비용보다 더 저렴하면
 a. 저장된 인접 도시로의 최소 이동 비용 준비물 1을 업데이트
 b. 인접 도시를 키로, 현재 도시를 값으로 하여 준비물2를 업데이트

4. 방문하지 않은 도시 중 비용이 가장 저렴한 도시에 방문해 현재 도시로 바꿔줍니다.

5. 알고있는 도시를 모두 방문할 때까지 2 ~ 4단계를 반복합니다.

 

이렇게 글로 설명하면 이해가 어려울 수 있습니다.

코드를 보겠습니다.

 

// 그래프 정점 클래스 선언
class City {
    name
    routes

    constructor(name) {
        this.name = name
        this.routes = new Map()
    }

    addRoute(city, price) {
        this.routes.set(city, price)
    }
}

// 그래프 초기화
atlanta = new City('atlanta')
boston = new City('boston')
chicago = new City('chicago')
denver = new City('denver')
el_paso = new City('Elpaso')

atlanta.addRoute(boston, 100)
atlanta.addRoute(denver, 160)
boston.addRoute(chicago, 120)
boston.addRoute(denver, 180)
chicago.addRoute(el_paso, 80)
denver.addRoute(chicago, 40)
denver.addRoute(el_paso, 140)

function djikstraShortestPath(startingCity, finalDestination) {
    // 출발지부터 해당 도시까지 드는 최소 비용 테이블
    const cheapestPriceTable = new Map()
    // 출발지부터 해당 도시까지 최소 비용으로 도달하는 마지막 경유지 테이블
    const cheapestPreviousThroughTable = new Map()
    // 방문 했던 도시 테이블
    const visitedCities = new Map()
    // 아직 방문하지 않은 도시 배열
    let unvisitedCities = []
    // 현재 방문중인 도시 변수
    // 출발지를 현재 방문 도시로 선정
    let currentCity = startingCity
    // 최소 비용 테이블에 출발지를 비용 0으로 추가 ( 인접 도시 비용 계산 위해서 )
    cheapestPriceTable.set(startingCity.name, 0)
    // 더이상 미방문 도시가 존재하지 않을 때까지 순회
    while (currentCity !== null) {
        // 현재 도시를 방문 도시 테이블에 추가
        visitedCities.set(currentCity.name, true)
        // 미방문 도시 배열에서 제거
        unvisitedCities = unvisitedCities.filter(city => city.name !==
                                                         currentCity.name)
        // 인접 도시 순회
        currentCity.routes.forEach((price, city) => {
            if(!visitedCities.has(city.name)) {
                // 미방문 도시에 추가
                unvisitedCities.push(city);
            }
            // 인접 도시 까지 최소 비용 계산
            const priceGoToAdjcentCity = cheapestPriceTable.get(currentCity.name) +
                                         price;

            // 최소 비용 테이블에 인접도시가 존재하지 않거나 최소 비용 테이블에 있는것보다 현재 도시를 경유한 비용이 더
            // 저렴한 경우   최소 비용 테이블 및 경유지 테이블을 업데이트
            if (!cheapestPriceTable.has(city.name) ||
                cheapestPriceTable.get(city.name) > priceGoToAdjcentCity) {
                cheapestPriceTable.set(city.name, priceGoToAdjcentCity)
                cheapestPreviousThroughTable.set(city.name, currentCity.name)
            }
        })
        // 현재 도시를 미방문 도시 중 비용이 가장 적은 도시로 설정
        let nextDestination = null;
        unvisitedCities.forEach(city => {
            nextDestination = nextDestination === null || cheapestPriceTable.get(nextDestination.name) >
                              cheapestPriceTable.get(city.name) ? city : nextDestination
        })
        currentCity = nextDestination;
    }
    // 최소 비용 경로 변수 생성
    const shortestPath = [];
    let currentCityName = finalDestination.name;
    while (currentCityName !== startingCity.name) {
        // 마지막 도시부터 최소 비용 경유지 테이블을 역산
        shortestPath.push(currentCityName)
        currentCityName = cheapestPreviousThroughTable.get(currentCityName)
    }
    shortestPath.push(startingCity.name)
    // 최소 비용 경로 변수 역순으로 반환
    return shortestPath.reverse()
}

console.log(djikstraShortestPath(atlanta, el_paso))

---

 

3. 데이크스타라 알고리즘의 효율성

데이크스트라 알고리즘은 가중 그래프에서 최단 경로를 찾는 방법을 설명할 뿐 코드 구현이 정형화되어있지 않습니다.
때문에 어떻게 구현하느냐에 따라 성능의 차이를 보일 수고 시간 복잡도로 표현하기 쉽지 않습니다.

앞선 코드에서 unvisitedCities의 자료구조를 단순 배열에서 우선순위 큐로 구현한다면 더 나은 성능을 보일 수 있습니다.