SSSP(Single-source shortest paths)

SSSP(Single-source shortest paths) 알고리즘이란?

어떤 그래프에서 시작 노드부터 도착 노드까지의 최단거리를 구하는 알고리즘이다.

SSSP 알고리즘은 대표적으로 3가지로 나눌 수 있다.

• 그래프에 음의 간선이 없는 경우
  • Dijkstra’s algorithm: O(|E| + |V| log |V|)
• 음의 사이클이 존재하지 않는 경우
  • Bellman-Ford algorithm: O(|V||E|)
• DAG(Directed Acyclic Graph, 유향 비순환 그래프)의 경우
  • One pass of Bellman-Ford: O(|V||E|)
  • DAG Shortest Path using Topological Sort: O(|V| + |E|)

다익스트라 알고리즘(Dijkstra's Algorithm)

dijkstra(G) {
    Q ← V // 우선순위 큐 Q에 모든 정점 V를 삽입
    d[v] ← ∞ for all v ∈ V // V의 모든 정점 v에 대해 d값을 무한대로 지정
    d[s] ← 0 for 임의의 s ∈ V // 시작 정점 s에 대해 d값을 0으로 지정
    while Q ≠ ∅
        // Q에 남은 정점 중 d값이 가장 작은 정점 u
        u ← EXTRACT_MIN(Q)
        // u에 연결된 정점 v에 대해
        for each v ∈ Adj[u]
            // v가 트리에 속해있지 않고 u와 v 사이의 가중치와 u의 d값의 합이 v의 d값보다 작다면
            if v ∈ Q and d[u] + w(u, v) < d[v]
                then d[v] ← d[u] + w(u, v) // v의 d값 초기화
}

의사 코드를 읽어보면 최소 신장 트리를 구하는 알고리즘 중에서 "프림 알고리즘"과 매우 유사하다.

음의 간선이 존재하는 경우 다익스트라 알고리즘을 사용할 수 없는 이유는 간단하다. 다음의 예제를 보자.

A에서 B로 가는 최단경로는 A ⇀ C ⇀ B 순서로 3이 나오는 것이 맞다. 하지만 다음의 계산 과정을 통해 답이 다르게 나온다.

알고리즘을 통해 구한 최단 거리 테이블을 보면 A에서 B로 가는 최단 경로의 값이 답과 다르게 7으로 나온다.

의사코드를 읽어보면 알 수 있듯이 이미 우선순위 큐 Q에서 빠진, 이미 d값이 정해진 정점은 다시 방문하지 않기 때문에 이런 오류가 발생하는 것인데 이미 A ⇀ B로 이동하면서 이미 B의 d값을 7로 초기화했기 때문에 해당 정점 B로 다시 이동할 수 없어서 A ⇀ C ⇀ B 순서로 3이 나올 수 없다.

추가적인 이해를 돕기 위해 백준 문제를 첨부한다.

https://www.acmicpc.net/problem/1753

1753번: 최단경로

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Vertex implements Comparable<Vertex> {
    int x, d;

    public Vertex(int x, int d) {
        this.x = x;
        this.d = d;
    }

    @Override
    public int compareTo(Vertex o) {
        return d - o.d;
    }
}

class Edge {
    int to, cost;

    public Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}

public class Main {

    public final static int INF = Integer.MAX_VALUE / 2;

    public static int v, e, k;
    public static ArrayList<Edge>[] edges;

    public static String dijkstra() {
        Vertex[] vertexes = new Vertex[v + 1];
        vertexes[k] = new Vertex(k, 0);
        for (int i = 1; i <= v; i++) {
            if (i == k) continue;
            vertexes[i] = new Vertex(i, INF);
        }
        PriorityQueue<Vertex> pqueue = new PriorityQueue<>();
        for (int i = 1; i <= v; i++) {
            pqueue.offer(vertexes[i]);
        }
        while (!pqueue.isEmpty()) {
            Vertex p = pqueue.poll();
            if (edges[p.x] != null) {
                for (Edge e : edges[p.x]) {
                    if (pqueue.contains(vertexes[e.to]) && e.cost + p.d < vertexes[e.to].d) {
                        pqueue.remove(vertexes[e.to]);
                        vertexes[e.to].d = e.cost + p.d;
                        pqueue.offer(vertexes[e.to]);
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= v; i++) {
            if (vertexes[i].d == INF) {
                sb.append("INF\n");
            } else {
                sb.append(vertexes[i].d).append("\n");
            }
        }
        return sb.toString();
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        edges = new ArrayList[v + 1];
        for (int i = 1; i <= v; i++) {
            edges[i] = new ArrayList<Edge>();
        }
        k = Integer.parseInt(br.readLine());
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            edges[u].add(new Edge(v, w));
        }
        System.out.print(dijkstra());
    }
}

벨만 포드 알고리즘(Bellman-Ford Algorithm)

벨만 포드 알고리즘은 위에서 설명한 다익스트라 알고리즘의 음의 간선이 존재할 수 없다는 가장 큰 문제점을 해결한 알고리즘이다.

bellman_ford(G) {
    d[v] ← ∞ for all v ∈ V // V의 모든 정점 v에 대해 d값을 무한대로 지정
    d[s] ← 0 for 임의의 s ∈ V // 시작 정점 s에 대해 d값을 0으로 지정
    for i ← 1 to |V| - 1
        for each e(u, v) ∈ E
            if not d[u] = ∞ and d[u] + w(u, v) < d[v]
                then d[v] ← d[u] + w(u, v)
    // 마지막에 for문을 다시 돌렸을 때 더 작아지는 값이 있다면 음의 사이클을 발견한 것
    for each e(u, v) ∈ E
        // 음의 사이클을 발견했다면
        if not d[u] = ∞ and d[u] + w(u, v) < d[v]
            then return false
    return true
}

하지만 이런 벨만 포드 알고리즘 또한 음의 사이클이 존재하는 경우에 사용할 수 없다는 그래프의 제한이 있다. 이유는 간단하다. 음의 사이클이 존재한다면 해당 정점으로 가는 최단 경로는 사이클을 돌 때마다 점점 더 작아지기 때문에 결국 음의 무한대로 발산하기 때문이다. 이해를 돕기 위해 백준 문제를 첨부한다.

https://www.acmicpc.net/problem/11657

11657번: 타임머신

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Edge {
    int from, to, cost;

    public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}

public class Main {

    final static int INF = Integer.MAX_VALUE;
    static int n, m;
    static long[] d;
    static ArrayList<Edge> edges;

    public static boolean bellmanFord() {
        Arrays.fill(d, INF);
        d[1] = 0;
        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (d[e.from] == INF) continue;
                d[e.to] = Math.min(d[e.to], d[e.from] + e.cost);
            }
        }
        for (Edge e : edges) {
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                System.out.println(-1);
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        edges = new ArrayList<>();
        d = new long[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges.add(new Edge(a, b, c));
        }
        if (bellmanFord()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= n; i++) {
                sb.append(d[i] != INF ? d[i] : -1).append("\n");
            }
            System.out.print(sb);
        }
    }
}

One pass of Bellman-Ford 알고리즘

DAG의 경우 사이클이 존재하지 않기 때문에 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 확인하는 과정을 줄이면 된다.

one_pass_of_bellman_ford(G) {
    d[v] ← ∞ for all v ∈ V // V의 모든 정점 v에 대해 d값을 무한대로 지정
    d[s] ← 0 for 임의의 s ∈ V // 시작 정점 s에 대해 d값을 0으로 지정
    for i ← 1 to |V| - 1
        for each e(u, v) ∈ E
            if not d[u] = ∞ and d[u] + w(u, v) < d[v]
                then d[v] ← d[u] + w(u, v)
}

DAG Shortest Path using Topological Sort 알고리즘

One pass of Bellman-Ford 알고리즘의 경우 그냥 벨만 포드 알고리즘과 시간 복잡도는 O(|V||E|)로 동일하다.

이러한 문제를 더 빠르게 위상정렬을 DAG에서 사용할 수 있다는 사실을 이용하여 해결할 수 있다.

topological_sort2(G, V) {
    for each v ∈ V {
    	visited[v] ← false;
    }
    for each v ∈ V {
        if visited[v] = false
            then dfs_tf(v);
    }
}
dfs_ts(v) {
    visited[v] = true;
    for each x ∈ adj[v] {
        if visited[x] = false
            then dfs_ts(x);
    }
    /* 스택 S에 push */
}
shortest_path(s) {
    d[v] ← ∞ for all v ∈ V // V의 모든 정점 v에 대해 d값을 무한대로 지정
    d[s] ← 0; // 시작 정점 s에 대해 d값을 0으로 지정
    while S ≠ ∅
        u ← S.pop()
        for each v ∈ adj[u] {
            if d[u] + w(u, v) < d[v]
                then d[v] ← d[u] + w(u, v)
        }
}