가중 그래프
가중 그래프(weighted graph)는 간선에 정보를 추가할 수 있는 유용한 그래프 유형이다.
정보에는 무게,거리나 비용같은 수치가 담길 수 있다. 가중 그래프를 쉽게 이해하기 위해 아래 미국의 도시 그래프를 보자.
각 간선에는 도시 간 거리가 마일 단위로 숫자가 붙어 있다. 뉴욕과 시카고의 거리는 714마일이다.
가중 그래프에는 위처럼 무방향 형태로 존재할 수 있으며, 방향이 존재할 수도 있다.
이처럼 정점 사이 간선에 여러 정보를 추가할 수 있는 그래프를 가중 그래프라고 한다. 이를 활용해서 까다로운 문제도 풀 수 있는데, 그 중에는 최단 경로를 산출함과 동시에 얼마만큼의 비용이 드는지 계산할 수 있다.
예를 들어, 위 이미지에서 애틀랜타에서 엘패소로 가는 가장 저렴한 경로를 알고 싶다고하자. 애틀랜타에서 엘페소로가는 직항이 없으니 경유해야한다.
어떻게 경유하는 것이 가장 저렴한 방법일까? 애틀랜타 -> 덴버 -> 엘페소 경로를 거친다면 총 300달러가 든다. 하지만 애틀랜타 -> 덴버 -> 시카고 -> 엘페소 경로는 280달러로 갈 수 있으므로 더 저렴한 경로이다.
이같은 목적지로 가는 최소 비용을 찾는 문제를 최단 경로 문제(Shortest Path Problem)라 부른다. 물론, 형태는 여러 가지를 띌 수 있다. 가장 짧은 경로를 찾는다던지, 오히려 비싼 경로를 찾는다던지.
데이크스트라 알고리즘
최단 경로 문제를 푸는 알고리즘에는 여러 가지가 있지만, 그 중 유명한 데이크스트라 알고리즘을 학습해보자.
다음 코드는 데이크스트라 알고리즘을 구현하기 위해 작성한 가중 그래프 클래스이다.
public class City {
// 이름
private String name;
// 경로
private Map<City, Integer> routes;
// 생성자
public City( String name ){
this.name = name;
routes = new HashMap<>();
}
//getter
public String getName() {
return name;
}
//getter
public Map<City, Integer> getRoutes() {
return routes;
}
/*
* 정점 추가 메서드
* */
public void addRoute( City city, int price ){
routes.put( city, price );
}데이크스트라 알고리즘은 모든 도시로 가는 가장 저렴한 비용을 찾을 수 있다. 가령 애틀랜타에서 시카고, 애틀랜타에서 덴버로 가는 최소 비용과 경로를 모두 알 수 있다.
이를 위해선 시작 도시에서 다른 목적지까지 가는 현재까지의 가장 저렴한 비용과 목적지까지의 직전 경유지을 저장할 수단이 필요한데, 본 포스팅에선 해시 맵을 사용할 것이다.
아래 이미지는 해시 맵을 표로 나타낸 것이다. 가장 저렴한 비용을 저장하는 해시 맵은 cheapestPricesTable라고 선언하고 직전 경유지를 저장하는 해시 맵은 cheapestPreviousStopoverCityTable라 선언할 것이다.
데이크스트라 알고리즘은 다음과 같은 단계로 진행된다.
-
시작 도시(정점)에 방문해 현재 도시(정점)으로 만든다.
-
현재 도시에서 각 인접 도시로의 비용을 확인한다.
-
시작 도시에서 인접 도시로의 비용이 현재 cheapestPricesTable의 비용보다 저렴하면(혹은 인접도시가 아직 cheapestPricesTable에 없으면)
- cheapestPricesTable을 더 저렴한 비용으로 수정한다.
- 인접 도시를 키로, 현재 도시를 값으로 해서 cheapestPreviousStopoverCityTable을 수정한다.
-
다음으로 시작 도시에서 방문하지 않은 도시 중 비용이 가장 저렴한 도시에 방문해 현재 도시로 만든다.
-
알려진 도시에 모두 방문할 때까지 2-4단계를 반복한다.
단계를 천천히 따라가며 알고리즘을 이해해보자.
먼저, 시작 도시인 애틀랜타에 방문해 currentCity로 만든다.
currentCity는 점선으로 표시되어있으며, 체크된 도시는 방문했던 도시이다.
이어서 currentCity의 각 인접 도시를 조사한다. 이전에 몰랐던 인접 도시가 있으면 맵에 추가하면서 새 도시를 계속 조사한다.
애틀랜타에서 보스턴까지 100달러이다. 이 비용이 애틀랜타에서 보스턴으로 가는 가장 저렴한 비용인지 cheapestPricesTable을 확인한다. 아직 애틀랜타에서 보스턴으로 가는 비용이 저장되지 않았으므로 cheapestPricesTable에 저장한다.
| 애틀랜타(출발지) | 보스턴 |
|---|---|
| $0 | $100 |
또한 인접 도시를 키로, 현재 도시를 값으로 하는 cheapestPreviousStopoverCityTable에도 저장한다.
| 애틀랜타부터 최소 비용으로 가는 직전 경유지 |
보스턴 |
|---|---|
| 애틀랜타 |
cheapestPreviousStopoverCityTable에 저장되어 있는 직전 경유지는 키에 해당하는 도시에 접근하기 위해선 먼저 값에 있는 도시에 접근해야함을 뜻한다. 보스턴에 가기 위해 애틀랜타에 먼저 경유해야한다는 뜻이다.
다음 인접 도시로는 덴버가 있다. 덴버로 가는 요금은 $160이며 보스턴과 마찬가지로 아직 cheapestPricesTable에 저장되어있지 않다. 덴버로 가는 가장 저렴한 비용을 160으로 저장한다.
| 애틀랜타(출발지) | 보스턴 | 덴버 |
|---|---|---|
| $0 | $100 | $160 |
cheapestPreviousStopoverCityTable에도 저장한다.
| 애틀랜타부터 최소 비용으로 가는 직전 경유지 |
보스턴 | 덴버 |
|---|---|---|
| 애틀랜타 | 애틀랜타 |
애틀랜타의 인접 도시를 모두 확인했다. 다음 도시로 넘어가야하는데, 다음 도시는 아직 방문하지 않은 도시만 방문해야하며, 시작 도시에서 갈 수 있는 현재까지의 가장 저렴한 도시를 '먼저' 방문해야 한다.
위 단계에서 아직 방문하지 않은 도시는 보스턴과 덴버이다. cheapestPricesTable에서 보스턴으로 가는 비용이 더 저렴하므로 보스턴을 방문한다.
위에서 진행한 단계를 반복한다.
보스턴을 방문하고 currentCity로 설정한다.
보스턴의 인접 도시를 모두 확인한다. 먼저 시카고를 보면 보스턴에서 시카고로 가는 요금은 $120이다. cheapestPricesTable에서 확인 했을 때, 애틀랜타에서 보스턴까지 가는 가장 저렴한 경로의 요금은 $100이므로, 애틀랜타에서 시카고로 가는 가장 저렴한 항공료는 $220이다.( 보스턴을 경유해 가므로 ) 그리고 다른 인접 도시인 덴버를 확인한다. 보스턴에서 덴버로 가는 요금은 $180이다. 똑같이 애틀랜타에서 보스턴을 거쳐 덴버로 가는 경로는 총 $280이다.
이 정보를 토대로 해시 맵에 정보를 저장한다. 먼저 시카고로 가는 요금은 총 $220이다. 이는 cheapestPricesTable에 저장되어 있지 않으므로 새로 저장한다. 그리고 보스턴을 경유해서 덴버로 가는 경로를 보면 총 $280이다. cheapestPricesTable에 확인해보면 $280보다 저렴한 $160이 이미 존재한 것을 확인 할 수 있다. 따라서 어떠한 수정도 하지 않는다.
| 애틀랜타(출발지) | 보스턴 | 덴버 | 시카고 |
|---|---|---|---|
| $0 | $100 | $160 | $220 |
| 애틀랜타부터 최소 비용으로 가는 직전 경유지 |
보스턴 | 덴버 | 시카고 |
|---|---|---|---|
| 애틀랜타 | 애틀랜타 | 보스턴 |
보스턴 인접 도시를 모두 확인했으니, 다음 도시를 방문할 차레다. 애틀랜타에서 시카고로 가는 비용($220)보다 덴버로 가는 비용($160)이 더 저렴하니 덴버를 방문한다.
덴버의 인접 도시는 시카고와 엘패소다. 애틀랜타에서 덴버를 경유하여 시카고로 가는 비용은 총 $200이다. cheapestPricesTable에서 애틀랜타에서 시카고로 가는 가장 저렴한 비용은 $220이다. $200이 더 저렴하니 해당 금액으로 cheapestPricesTable을 수정한다. 또한, cheapestPreviousStopoverCityTable도 수정한다.
| 애틀랜타(출발지) | 보스턴 | 덴버 | 시카고 |
|---|---|---|---|
| $0 | $100 | $160 | $200 |
| 애틀랜타부터 최소 비용으로 가는 직전 경유지 |
보스턴 | 덴버 | 시카고 |
|---|---|---|---|
| 애틀랜타 | 애틀랜타 | 덴버 |
덴버에서 엘패소로 가는 총 금액은 $160 + $140이므로 $300이다. 이 데이터도 해시 맵에 저장한다.
| 애틀랜타(출발지) | 보스턴 | 덴버 | 시카고 | 엘패소 |
|---|---|---|---|---|
| $0 | $100 | $160 | $200 | $300 |
| 애틀랜타부터 최소 비용으로 가는 직전 경유지 |
보스턴 | 덴버 | 시카고 | 엘패소 |
|---|---|---|---|---|
| 애틀랜타 | 애틀랜타 | 덴버 | 덴버 |
인접 도시를 모두 확인했으니 방문할 차례다. 엘패소보다 시카고로 가는 비용이 더 저렴하니 시카고를 방문하고 currentCity를 시카고로 설정한다.
시카고의 인접 도시를 확인한다. 시카고는 인접 도시가 엘페소 하나뿐이다.
시카고에서 엘페소로 가는 비용을 확인하니 $80이다. 애틀랜타에서 덴버, 시카고를 경유해 엘페소를 가는 비용은 $160 + $40 + $80 = $280이다.
cheapestPricesTable에서 엘페소로 가는 현재까지의 최소 비용을 보자. $300으로 저장되어있다. 하지만 방금 덴버, 시카고를 경유해 엘페소를 가는 비용은 $280이란 것을 알게되었다. $280은 $300보다 저렴하므로 cheapestPricesTable를 $280으로 수정한다. 또한, cheapestPreviousStopoverCityTable도 수정한다.
| 애틀랜타(출발지) | 보스턴 | 덴버 | 시카고 | 엘패소 |
|---|---|---|---|---|
| $0 | $100 | $160 | $200 | $280 |
| 애틀랜타부터 최소 비용으로 가는 직전 경유지 |
보스턴 | 덴버 | 시카고 | 엘패소 |
|---|---|---|---|---|
| 애틀랜타 | 애틀랜타 | 덴버 | 시카고 |
시카고에는 엘페소 외에 인접 도시가 없으므로 다음 도시를 방문한다.
방문하지 않은 유일한 도시는 엘페소이다. 엘페소를 방문하고 currentCity로 만든다.
엘페소의 인접 도시는 보스턴 하나이다. 요금은 $100이며 cheapestPricesTable를 참고했을 때 엘페소로 가는 가장 저렴한 비용은 $280이므로 엘페소를 경유한 보스턴으로 가는 요금은 $100 + $280 = $380이 든다. 요금 해시 맵을 봤을 때 보스턴으로 가는 가장 저렴한 요금은 $100이므로 어떤 수정도 하지 않는다.
모든 탐색이 끝났다. 이제 목적지까지 가기 위한 최소 비용 경로를 알 수 있다.
출발지에서 목적지까지의 경로는 cheapestPreviousStopoverCityTable을 참고하여 알 수 있는데, 가령 목적지인 엘패소를 key로 시카고를 얻을 수 있다. 그 다음은 시카고를 key로 덴버를 얻을 수 있다. 이런 식으로 목적지부터 출발지까지 거슬러 올라가면 최소 비용 경로를 알 수 있다.
최소 비용 경로는 애틀랜타 -> 덴버 -> 시카고 -> 엘페소이다.
코드 구현 - 데이크스트라 알고리즘
다음은 자바로 구현한 데이크스트라 알고리즘이다. 처음에 작성한 가중 그래프 클래스와 연계된다. (많이 길다..)
/*
* 데이크스트라 알고리즘
* */
public void dijkstraShortestPath( City startingCity, City finalDestination ){
Map<String, Integer> cheapestPricesTable = new HashMap<>();
Map<String, String> cheapestPreviousStopoverCityTable = new HashMap<>();
// 아직 방문하지 않은 알려진 도시를 단순 배열에 기록한다.
List<City> unvisitedCities = new ArrayList<>();
// 방문했던 도시를 해시 맵에 기록한다.
Map< String, Boolean > visitedCities = new HashMap<>();
// cheapestPricesTable의 첫 번째 키로
// 시작 도시의 이름을 추가한ㄷ.
// 시작 도시로 가는 비용은 없으니 값은 0이다.
cheapestPricesTable.put(startingCity.name, 0);
City currentCity = startingCity;
// 방문하지 않은 도시가 남아 있는 동안 실행된다.
while( currentCity != null ){
// visitedCities 해시에 currentCity의 이름을 추가해
// 방문했음을 기록한다.
// 또한 unvisitedCities 리스트에서는 제거한다.
visitedCities.put(currentCity.name, true);
unvisitedCities.remove(currentCity);
// currentCity의 인접 도시를 각각 순회한다.
for( Map.Entry<City,Integer> adjacentCity : currentCity.routes.entrySet() ){
// 새 도시를 발견하면
// unvisitedCities 리스트에 추가한다.
if( !visitedCities.containsKey(adjacentCity.getKey().name) )
unvisitedCities.add(adjacentCity.getKey());
// CURRENT city를 마지막으로 경유하는 도시로 사용해
// STARTING city에서 ADJACENT city로 가는 비용을 계산한다.
int priceThroughCurrentCity
= cheapestPricesTable.get(currentCity.name) + adjacentCity.getValue();
// STARTING city에서 ADJACENT city로 가는 비용이
// 지금까지 알려진 비용보다 저렴하면
if( !cheapestPricesTable.containsKey(adjacentCity.getKey().name) ||
priceThroughCurrentCity < cheapestPricesTable.get(adjacentCity.getKey().name)){
// 두 표를 업데이트한다.
cheapestPricesTable.put(adjacentCity.getKey().name, priceThroughCurrentCity);
cheapestPreviousStopoverCityTable.put(adjacentCity.getKey().name, currentCity.name);
}
}
// 방문하지 않은 다음 도시를 방문한다.
// STARTING city에서 갈 수 있는 가장 저렴한 도시로 선택한다.
currentCity = unvisitedCities.stream()
.min( (city1, city2) ->
Integer.compare( cheapestPricesTable.get(city1.name), cheapestPricesTable.get(city2.name) ))
.orElse(null);
}// end while
// 이제 cheapestPricesTable은 starting city에서 각 도시로 가는
// 가장 저렴한 비용을 모두 포함한다. 하지만 starting city에서
// final destination으로 가는 정확한 경로를 계산하려면 다음 단계로 가야한다.
// 리스트로 최단 경로를 생성한다.
List<String> shortestPath = new ArrayList<>();
// 최단 경로를 구성하려면 final destination에서부터
// 거슬러 올라가야 한다. currentCity을
// final destination으로 시작한다.
String currentCityName = finalDestination.name;
// startingCity에 도달할 때까지 루프를 실행한다.
while( currentCityName != startingCity.name ){
// 도시가 나올 때마다 각 currentCityName을 shortestPath 리스트에 추가한다.
shortestPath.add(currentCityName);
// cheapestPreviousStopoverCityTable 을 사용해
// 바로 이전 경유 도시를 따라간다.
currentCityName
= cheapestPreviousStopoverCityTable.get(currentCityName);
}
// 마지막으로 startingCity를 shortestPath에 추가한다.
shortestPath.add(startingCity.name);
// 시작부터 끝까지 순서대로 경로를 나타내기 위해 출력을 뒤집는다.
for( int i = 1; i <= shortestPath.size(); i++ )
System.out.println(shortestPath.get(shortestPath.size() - i));
}아래의 샘플코드로 테스트도 해보자.
public static void main(String[] args) {
City atlanta = new City("Atlanta");
City boston = new City("Boston");
City chicago = new City("Chicago");
City denver = new City("Denver");
City el_paso = new City("El Paso");
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);
atlanta.dijkstraShortestPath( atlanta, el_paso );
}데이크스트라 알고리즘의 효율성
방문하지 않은 도시를 저장하는 unvisitedCities를 리스트로 사용하면 알고리즘에 최대 O(V²)이 걸린다. 모든 정점마다 그 정점에서 인접 정점으로의 가중치를 매번 확인해야하기 때문이다. 이는 정점 을 뜻하는 V²이 걸린다.
나가는 글
사실 unvisitedCities를 리스트대신 우선순위 큐로 구현하면 더 빠르다. 이것이 중요한 점이다. 알고리즘의 각 로직을 분석하고 최적의 자료구조를 선택하는 것. 그래프에도 여러가지 알고리즘과 다른 구현 법이 수두룩한데, 최적의 자료구조와 단순한 로직을 구현하는 것이 중요한 능력이 될 것 같다.
그리고... 알고리즘이 너무 복잡해서 내가 최적화를 시도 해볼 수 있을까 의문이다...
