[알고리즘] 최단 경로 알고리즘 - 다익스트라, 벨만 포드 ,플로이드 알고리즘

최단 경로 알고리즘이란?

주어진 그래프에서 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제입니다.

실제로 그래프의 응용문제 가운데 가장 유용하고 널리 사용됩니다.
(그래도 DFS가 전 편하더라구요..)

뭐 설명할게 딱히 없네요 😢

대표적인 최단 경로 알고리즘

최단 경로 알고리즘은 대표적으로 3가지가 있습니다.

• 다익스트라 알고리즘 (default)
• 벨만 포드 알고리즘 (distance 값이 0이하가 존재할 때)
• 플로이드 알고리즘 (모든 시작점에 대해, 소스 코드 간단)

간단하게 하나하나 씩 짚고 넘어가보겠습니다.

다익스트라 알고리즘

다익스트라 알고리즘은, 음 뭐랄까,,, 가장 기초적인 두 정점간의 최단거리를 구하는 알고리즘입니다.
구현하는 방법은 집합으로 푸는 방식, 우선순위 큐 (Heap) 를 쓰는 방식이 존재합니다.

사실 기존에는 집합으로 푸는 방식을 선호했는데, 이번에는 우선순위 큐를 쓰는 방식으로 구현 해볼게요.

다익스트라 알고리즘의 가장 큰 매커니즘은 다음과 같습니다

$distance[a][c] > distance[a][b] + distance [b][c]$ 가 성립한다면
$distance[a][c] = distance[a][b]+distance[b][c];$

즉 무슨 말이냐면 a와 c 사이에 경로를 한번에 가는것보다 b를 우회해서 가는 경로가 더 효율적인 경우 대체 하겠다는 겁니다. (오 매우 합리적) 😃

집합으로 푸는 방식은 위 공식 하나로 끝이 났는데,
우선순위 큐를 사용해서 해결하는 방식은 여기서 한가지를 더 기억해야 합니다!!
기존의 우선순위 큐에 있는 녀석 보다 짧은 경로가 큐에 들어올 경우 먼저 들어온 녀석을 어떻게 처리할 건지에 대해 정의해야합니다.

종만북에서는 2가지 방법을 제시하고 있는 방법은 다음과 같습니다!

• 기존의 존재하고 있는 경로를 찾아내 짧은 경로로 변경한다.
• 기존의 경로를 그대로 두고 짧은 경로를 추가한다. 그리고 큐에서 처리할 때 먼저 들어온 경로를 무시한다.

기본적으로 후자가 많이 쓰인다고들 합니다!👍👍

최단거리 알고리즘의 구현은 다음과 같습니다!

class Pair implements Comparable<Pair>{
    int vertex;
    double distance;
    
    Pair(int v, double d){
    	vertex = v;
        distance = d;
        }
   	
    @Override
    public int compareTo(Pair o){
    return (int)(distance - o.distance);
    }
 }
 
 double dijkstra(){
    double[] distance = new double[vertexNum];
    Arrays.fill(distance,Double.MAX_VALUE);
    PriorityQueue<Pair> heap = new PriorityQueue<>();
    heap.add(new Pair(0,distance[0]]);
    while(!heap.isEmpty()){
        Pair p = heap.poll();
        if(distance[p.vertex] < p.distance) continue;
        for(int i : graph.get(p.vertex).keySet()){
            if(distance[i] > distance[p.vertex] + graph.get(p.vertex).get(i)){
                distance[i] = distance[p.vertex] + graph.get(p.vertex).get(i);
                heap.add(new Pair(i,distance[i]));
                }
            }
    }
    return distance[vertexNum-1];

다익스트라 알고리즘의 시간 복잡도

$O(|E|+|E|lg|E|) = O(|E|lg|E|)$ 가 됩니다.

n lg n 이면 상당히 괜찮네요!!

위와 같은 결과가 나오는 이유는 다음과 같습니다

• 모든 간선들을 검사하는데 드는 시간 E
• 우선순위 큐에 원소를 추가하거나 삭제하는데 걸리는 시간 lgE (heap 특성상)

그래서 위와 같은 결과가 나오는거죠^^ 🤔

벨만 포드 알고리즘

다익스트라의 경우 최단 경로를 구하는데 있어서 가장 default 하지만,
음수 간선이 있는 경우에는 앞서 말했던 공식이 성립 하지 않습니다.

(distance[u][v] 므시기 했던거 있지 않습니까?!) <= 음수 간선이 존재하는 경우 그거 성립안합니다.

그래서 벨만포드 알고리즘을 알아두어야 해요 😭😭

벨만포드의 핵심은 최단거리 값의 비교를 통한 것입니다.

최단 거리[u] 와 최단거리[v]가 존재한다고 하면 다음과 같은 공식이 성립하죠

$dist[v] <= dist[u] + w(u,v)$ // dist[n]은 n까지의 최단거리

이 공식은 무조건 성립할 수 밖에없습니다
출발점 s 에서 v로 까지 가는 최단거리는 이미 최단거리 v라고 규정지은 dist[v]로 가는 것이 가장 빠를 것이니까요.

그런데 우리는 여기서 upper를 이용해 봅시다!!

$upper[v] <= upper[u] + w(u,v)$ 가 성립하지 않는 경우가 생긴다면?
그건 바로 $w(u,v) < 0$ 일때!!

그럼 구현으로 넘어가도록 하겠습니다.

public class BellmanFord {
    int vertexNum;
    int edgeNum;
    HashMap<Integer, Double>[] graph; //graph[출발지] = HashMap<도착지, 가중치>
    Double[] distance;
    
    public double bellmanFord(){
        distance[0] = 0.0;
        for(int i=1; i<vertexNum; i++) distance[i] = Double.MAX_VALUE;
        
        boolean update = false;
        for(int i=0; i<vertexNum; i++){
            update = false;
            for(int vi=0; vi<vertexNum; i++){
                for(int adj : graph[vi].keySet()){
                    if(distance[adj] > distance[vi] + graph[vi].get(adj)){
                        distance[adj] = distance[vi] + graph[vi].get(adj);
                        update = true;
                    }
                }
            }
            if(!update) break; //완화를 전부 
        }
        if(update) return Integer.MAX_VALUE; //(VertexNum - 1)번 한 후 완화 가능하면 사이클이 존재하는 것
        return distance[edgeNum - 1];
    }
}

출처 : https://doublezerostone.tistory.com/29

플로이드 알고리즘

사실 플로이드 알고리즘은 설명할 것이 없습니다.

다익스트라 알고리즘을 모든 시작점에서 시작해서 다른 정점까지 반복문을 돌린다고 보면 되거든요,,

그래서 주로 for문이 3중으로 발생하는 경우가 생깁니다.

Floyd 알고리즘은 행렬로 푸는 경우가 많아서 행렬로 구현할께요!

기본적인 구조는 다음과 같습니다.

for(int k = 0; k<graph.length; k++)
  for(int u = 0; u<graph.length; u++)
      for(int w = 0; w<graph.length; w++)
        if(distance[u][w] < distance[u][k] + distance[k][w])
            distance[u][w] = distance[u][k] + distance[k][w];
        

다익스트라에서 언급한 공식이 위에 그대로 나왔죠^^?

넵 보여드릴게 없습니다.

대신 시간복잡도는 3중 for문이기 때문에 $O(n^3)$으로써 효율이 좋은 편은 아니라고 말씀드리고 싶습니다!
(모든 정점에 대해서 처리하니 그부분에선 빠르다고 할 수 있죠!)