13. 최단거리 문제

  이번에는 조금 더 어려운 이야기를 해보자. 이번 시간에는 그래프에 대한 지식이 살짝 필요하니 모르시는 분들은 미리 사전 학습을 해보시는 걸 추천합니다.

(그래프 위키 백과 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84)

  임의의 그래프에서 최단거리를 구하는 방법을 알아 보자. 최단거리 문제를 푸는 대표적인 2가지 방법은 다익스트라 알고리즘과, 워셜-플로이드 알고리즘이 존재한다.

1. 다익스트라 알고리즘 (Dijkstra algorithm)

  다익스트라 알고리즘을 적용하기 위해선 아래의 조건을 만족하는 그래프여야한다.

• 음의 가중치를 가지는 edge가 있어서는 안된다.

  

 다익스트라 문제를 풀기 위해 아래와 같은 그래프를 예시로 들어 문제를 해결하자.

  위 그래프에 대한 거리를 구하는 배열을 작성하면 다음과 같다.

  이제 다익스트라 알고리즘을 적용해보자. 노드 1번부터 6번까지 가는 최단 거리를 구하려고 하고, 기호로 P[1][6]으로 표기한다.

출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값을 입력한다.

  출발 노드에서 갈 수 있는 인접 미방문 노드에 대한 거리를 계산한다. 인접 미방문 노드란 현재 노드에 인접한 노드 중 아직 방문하지 않는 곳을 의미한다. 현재 위치는 1번 노드이고, 갈 수 있는 인접 2번 노드에 대하여 최단 거리인 2를 입력한다. 마찬가지로 인접 미방분 노드인 3번 노드도 6을 입력한다. 

  시작 점인 1번 노드로 부터 인접한 노드에 대한 거리를 모두 입력했기에 다음 노드인 2번으로 방문해보자. 다익스트라의 원리는 간단하다. 현재 노드 A에 인접한 노드 B가있을 때, d[A] + P[A][B] 값과 d[B] 값을 비교하여 큰 값을 입력하면 된다. 2번 노드에 인접한 노드는 1,4,5번 노드가 있다. 첫번째 노드인 1번을 살펴보면, d[2]의 값은 현재 2이고, P[2][1]은 2, d[1]은 0이다. d[2]+P[2][1] = 4이고, d[1]=0이므로 두 값 중 작은 d[1]을 채택하여 그대로 둔다. 만약 d[2]+P[2][1]값이 작았다면 d[1]에 새로 값을 수정한다. 4번, 5번 노드에 대해서도 이 과정을 반복한다.

 

  2번 노드에 대한 방문이 끝났으니, 3번 노드에 방문 과정을 반복한다. 최종적으로 아래와 같은 표가 나올 것이다.

  

  시작 노드 1부터 6까지의 최단 거리는 7이라는 점을 알 수 있다.

  시작 노드로 부터 인접한 노드에 대한 계산을 반복하는 구조기 때문에 시간복잡도는 기본적으로 O(V^2)가 된다. 해당 코드를 Java로 구현한다면 아래와 같이 나올 것이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
 
public class Dijkstras {
 
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addVertex('A', Arrays.asList(new Vertex('B', 7), new Vertex('C', 8)));
        g.addVertex('B', Arrays.asList(new Vertex('A', 7), new Vertex('F', 2)));
        g.addVertex('C', Arrays.asList(new Vertex('A', 8), new Vertex('F', 6), new Vertex('G', 4)));
        g.addVertex('D', Arrays.asList(new Vertex('F', 8)));
        g.addVertex('E', Arrays.asList(new Vertex('H', 1)));
        g.addVertex('F', Arrays.asList(new Vertex('B', 2), new Vertex('C', 6), new Vertex('D', 8), new Vertex('G', 9), new Vertex('H', 3)));
        g.addVertex('G', Arrays.asList(new Vertex('C', 4), new Vertex('F', 9)));
        g.addVertex('H', Arrays.asList(new Vertex('E', 1), new Vertex('F', 3)));
        System.out.println(g.getShortestPath('A', 'H'));
    }
    
}
 
class Vertex implements Comparable<Vertex> {
    
    private Character id;
    private Integer distance;
    
    public Vertex(Character id, Integer distance) {
        super();
        this.id = id;
        this.distance = distance;
    }
 
    public Character getId() {
        return id;
    }
 
    public Integer getDistance() {
        return distance;
    }
 
    public void setId(Character id) {
        this.id = id;
    }
 
    public void setDistance(Integer distance) {
        this.distance = distance;
    }
 
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((distance == null) ? 0 : distance.hashCode());
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex other = (Vertex) obj;
        if (distance == null) {
            if (other.distance != null)
                return false;
        } else if (!distance.equals(other.distance))
            return false;
        if (id == null) {
            if (other.id != null)
                return false;
        } else if (!id.equals(other.id))
            return false;
        return true;
    }
 
    @Override
    public String toString() {
        return "Vertex [id=" + id + ", distance=" + distance + "]";
    }
 
    @Override
    public int compareTo(Vertex o) {
        if (this.distance < o.distance)
            return -1;
        else if (this.distance > o.distance)
            return 1;
        else
            return this.getId().compareTo(o.getId());
    }
    
}
 
class Graph {
    
    private final Map<Character, List<Vertex>> vertices;
    
    public Graph() {
        this.vertices = new HashMap<Character, List<Vertex>>();
    }
    
    public void addVertex(Character character, List<Vertex> vertex) {
        this.vertices.put(character, vertex);
    }
    
    public List<Character> getShortestPath(Character start, Character finish) {
        final Map<Character, Integer> distances = new HashMap<Character, Integer>();
        final Map<Character, Vertex> previous = new HashMap<Character, Vertex>();
        PriorityQueue<Vertex> nodes = new PriorityQueue<Vertex>();
        
        for(Character vertex : vertices.keySet()) {
            if (vertex == start) {
                distances.put(vertex, 0);
                nodes.add(new Vertex(vertex, 0));
            } else {
                distances.put(vertex, Integer.MAX_VALUE);
                nodes.add(new Vertex(vertex, Integer.MAX_VALUE));
            }
            previous.put(vertex, null);
        }
        
        while (!nodes.isEmpty()) {
            Vertex smallest = nodes.poll();
            if (smallest.getId() == finish) {
                final List<Character> path = new ArrayList<Character>();
                while (previous.get(smallest.getId()) != null) {
                    path.add(smallest.getId());
                    smallest = previous.get(smallest.getId());
                }
                return path;
            }
 
            if (distances.get(smallest.getId()) == Integer.MAX_VALUE) {
                break;
            }
                        
            for (Vertex neighbor : vertices.get(smallest.getId())) {
                Integer alt = distances.get(smallest.getId()) + neighbor.getDistance();
                if (alt < distances.get(neighbor.getId())) {
                    distances.put(neighbor.getId(), alt);
                    previous.put(neighbor.getId(), smallest);
                    
                    forloop:
                    for(Vertex n : nodes) {
                        if (n.getId() == neighbor.getId()) {
                            nodes.remove(n);
                            n.setDistance(alt);
                            nodes.add(n);
                            break forloop;
                        }
                    }
                }
            }
        }
        
        return new ArrayList<Character>(distances.keySet());
    }
    
}

(출처 : https://github.com/mburst/dijkstras-algorithm/blob/master/Dijkstras.java)

2. 플로이드-워셜 알고리즘 (Floyd-warshall Algorithm)

  플로이드-워셜 알고리즘 역시 다익스트라와 더불어 최단거리를 구하는 또 하나의 알고리즘이다. 두 방식의 가장 큰 차이점은 플로이드-워셜 알고리즘은 다익스트라와 달리 음수 가중치가 있는 경우도 구할 수 있다.

  기본 원리는 매우 간단하다. 노드 A부터 B까지의 최단 거리를 구한다고 할때, A와 B사에 있는 모든 노드 m에 대해, d[A][B]의 값과, d[A][m] + d[m][B]를 구하면 된다. 두 값중 작은 값을 구해 d[A][B]로 설정한다. 따라서, 기본 원리는 다익스트라보다 더욱 간단하다. for문 세번만 중첩한다면 쉽게 구한다. 물론, for문이 3개이기 때문에 상당한 과부화가 걸릴 수 있다는 점도 존재한다.

  Pseudo Code는 위와 같이 구할 수 있다. 다익스트라보다 훨씬 직관적으로 구할 수 있으나, 최단 거리를 구하는데 필요한 여러가지 불필요한 연산이 추가 된다는 단점이 존재한다. Java를 통해 구현하면 아래의 코드가 나온다.

public class FloydWarshallAlgorithm {
    //private static final int MAX = 8;
    
    private double[][][] res;
    private double[][][] sequence;
    
    public FloydWarshallAlgorithm(int value, String[] vertex, Double[][] edges) {
        
        res = new double[value + 1][value][value];
        sequence = new double[value + 1][value][value];
        
        for (int i = 0; i < value; i++) {
            for (int j = 0; j < value; j++) {
                res[0][i][j] = edges[i][j];
                
                if(i == j)
                    sequence[0][i][j] = 0;
                else
                    sequence[0][i][j] = j + 1;
            }
        }
 
        int x = 1;
 
        for (int k = 0; k < value; k++) {
            for (int i = 0; i < value; i++) {
                for (int j = 0; j < value; j++) {
                    
                    sequence[x][i][j] = sequence[x - 1][i][j];
 
                    if (edges[i][j] > edges[i][k] + edges[k][j]) {
                        edges[i][j] = edges[i][k] + edges[k][j];
                        sequence[x][i][j] = x;
                    }
          
                    res[x][i][j] = edges[i][j];
                }
            }
 
            x++;
        }
    }
    
    public double[][][] getPath()
    {
        return res;
    }
    
    public double[][][] getSequence()
    {
        return sequence;
    }
}

(출처 : https://github.com/afifaniks/FloydWarshallSimulation/blob/master/src/floyd/warshall/FloydWarshallAlgorithm.java)

  최단 거리를 구하는 2가지 대표적인 알고리즘에 대해 배웠다. 이 중 다익스트라 알고리즘은 Greedy 알고리즘에 속한다. 바로 다음시간에 소개할 알고리즘이 바로 Greedy이다. 자세한 내용은 다음 시간에 설명하겠습니다.

P.S. 코드 구현 과정이 다소 어렵고 오래 걸리기에 Github에 존재하는 코드로 대체 했다는 점은 양해를 부탁드립니다.