# 개요


최단 경로 문제 정리

단어가 좀 혼용될 수 있다

  • Ex) 노드==정점 / 간선==엣지 

 

# 최단 경로 문제


가중치가 있는 방향/무방향 그래프에서 두 노드 사이의 가장 짧은 경로를 찾는 문제

 

# 최단 경로 문제의 유형


Single-Source / Single-Destination (One - to - All)

  • 하나의 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 문제
  • 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 문제
  • 방향을 뒤집으면 서로 같아지기 때문에 사실상 같은 유형으로 본다.
  • Dijkstra 알고리즘, Bellman Ford 알고리즘

 

All-Pairs (All - to - All)

  • 모든 노드 쌍에 대하여 최단 경로를 찾는 문제
  • Floyd-Warshall 알고리즘

 

# 최단경로와 음수 가중치


Dijkstra 알고리즘은 음수 가중치가 있을 경우 작동하지 않는다.

Bellman-Ford와 Floyd-Warshall 알고리즘은 음수 사이클이 없다는 가정하에 음수 가중치가 있어도 작동한다.

 

음수 사이클

음수 사이클이 있으면 최단 경로가 정의되지 않는다.

  • 사이클의 합이 음수라면 계속 사이클을 돌게 되고 결국 합이 -∞되어 최단 경로를 찾을 수 없다.
  • 단, 그래프 내에 음수 사이클이 있어도 그 사이클이 목적지까지 가는 경로에 없다면 상관없다.

 

# 최단 경로 문제의 기본 특성


1. 최단 경로의 어떤 부분 경로 역시 최단 경로이다. (Optimal SubStructure → DP)

  • 위 경로가 u → v의 최단 경로라면, x → y의 경로 또한 최단 경로이다.

 

증명 (귀류법)

  • 만약 더 짧은 경로(x → y)가 있다고 가정해보자
  • 이 경로가 더 짧다면 u → v의 최단 경로는 u → v가 아니라 x → y를 거쳐가는 u → x → y → v가 될 것이다.
  • 이것은 처음 가정(u →v 가 최단 경로라면)의 모순이 된다.
  • 그러므로 최단 경로의 부분 경로도 최단 경로이다.

 

2.  최단 경로는 사이클을 포함하지 않는다.

 

# Single-Source 최단 경로 문제


음수 사이클이 없는 가중치 방향 그래프 G = (V, E)와 출발 노드 S에서 각 노드 v에 대하여 다음을 계산한다.

  • d[v] (distance estimation): 출발 노드 S로부터 각 노드v에 대하여 현재까지 알고 있는 최단 경로의 길이 ( 알고리즘이 진행됨에 따라 갱신 된다.)
    • 처음에는 d[S] = 0, 각 d[v]들은 ∞으로 초기화한다.
      • S는 출발 노드이고, 음수 사이클이 없으므로 가장 작은 값인 0
      • 그 외의 다른 노드들 v는 아직 탐색 시작을 안했으므로 ∞
    • 알고리즘이 수행됨에 따라 d[v]가 점점 감소하며 최종적으로 d[v]값이 S →  v의 최단 경로 길이가 된다.
  • π[v] (predecessor): S에서 v까지의 최단 경로 상에서 v의 직전 노드
    • 처음에는 π[v]와 π[S]는 null로 초기화
      • 출발 노드S의 이전 노드는 없으므로 null
      • 다른 노드들 v는 아직 탐색 시작을 안했으므로 null
    • 최단경로의 길이 외에 그 경로 자체를 요구할 수 있으므로 이전 노드를 기록하며 역추적한다.

 

기본 연산: Relaxation

1. d[u] = 5, d[v] = 9, w(u,v) = 2(간선 u → v의 가중치 값)인 상황

  • d[v]는 "현재까지 알고 있는" S → v의 최단 경로 길이 이므로 Relaxation 연산에  따라 갱신 될 수 있다.
  • 기존에 알고 있는 S →  v의 최단 경로는 S →  v로 d[v] = 9 였는데 더 짧은 경로인 S → u → v경로를 발견했으므로 d[v] = d[u] + w(u,v)로 갱신한다 (9 > 5+2)

2. d[u] = 5, d[v] = 6, w(u,v) = 2인 상황

  • Relaxation 연산을 했지만 기존 최단 경로인 S → v d[v]가 더 짧은 경로이므로 갱신하지 않는다.

Relaxtaion 의사 코드

Relax(u, v, w) {
	if(d[v] > d[u] + w(u,v))
    	then d[v] ← d[u] + w(u,v)
        	 π[v] ← u
}

 

대부분의 Single-Source 최단 경로 알고리즘의 기본 구조

  1. 초기화: d[S] = 0, 노드 v에 대해 d[v] = ∞, π[v]=null
  2. 간선들에 대해서 반복적인 Relaxtation 연산

의사 코드

Generic-Single-Source(G, w, S) {
	Init(G, S)
    Repeat
    	for each edge(u,v)
        	Relax(u,v,w)
    until there is no change
}
  1. 의문: 이렇게 반복하면 최단 경로가 정말 찾아질까?
  2. 의문: 찾아진다면 몇 번 반복해야 찾아질까?

증명

  • 가정: N개의 정점에서, S → vn 경로가 최단 경로라면 이 경로에 포함된 간선의 개수는 최대 N-1개이다.
  • 첫 번째 Round
    • 모든 간선들에 대해 Relax연산을 하고, d[S] = 0, d[v1]이  ∞에서 d[S] + w(S, v1)을 통해 갱신 된다.
    • S → vn까지의 최단 경로의 부분 경로 역시 최단 경로이므로 갱신 된 d[v1]이 곧 최단 경로가 된다.
  • 두 번째 Round
    • 모든 간선들에 대해 Relax연산을 하고, d[v2]이  ∞에서 d[v1] + w(v1, v2)을 통해 갱신 된다.
    • 마찬가지로 갱신 된 d[v1]이 곧 최단 경로가 된다.
  • 반복하면 d[vn]은 n-1번째 Round에 최단 경로가 된다.
  • 즉 노드의 개수가 N개라면 N-1번의 반복으로 모든 노드의 최단 경로를 구할 수 있다.

직관적으로 봐도 vn까지 최단 경로의 간선 수는 최대 N-1라는 것을 생각할 수 있는데

  • vx를 거쳐가는 더 짧은 경로가 있다면? → 그럼 그 경로가 최단 경로가 되며, N개의 정점에서 N+1개의 정점이 되었다. 그러므로 간선의 개수는 최대 N개가 될 것이다.

  • v2 → v3 → v4 경로를 통해 가는 것보다 v3 → v2 갔다가 다시 v2 → v3으로 가는 것이 더 빠르다면? → 그 자체로 음수 사이클이 생긴다는 뜻이며 음수 사이클이 없다는 전제에 모순된다.

Worst Case

시간 복잡도: O(n^3) → 효율적인 알고리즘이라고 할 수 없다.

다음과 같은 상황을 보자

  • 첫 번째 Round에서 간선들을 어떠한 순서로 Relax 연산을 하다보니 d[v] = 1000이 되었다.
  • 두 번째 Round에서 간선들을 어떠한 순서로 Relax 연산을 하다보니 d[v] = 800이 되었다.
  • 최악의 상황은 마지막 Round에서 d[v] = 200으로 갱신 되고 이것이 최단 경로라는 것을 알게 되었을 때이다. 그제서야 v 이후의 노드들에 대한 최단 경로를 알 수 있게 된다.
  • 하지만 처음부터 가중치가 50인 경로로 Relax를 했다면 더 빠르게 최단 경로를 찾을 수 있지 않았을까?
    • Dijkstra 알고리즘으로 해결
  • 최악의 경우 시간 복잡도가 O(n^3)인데도 사용하는 이유는 가중치가 음수일 때도 동작하고, 음수 사이클 여부를 알 수 있기 때문이다.

 

# Reference

권오흠 교수님 유튜브 및 강의자료

 

1. 문제

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

 

1738번: 골목길

첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로

www.acmicpc.net

문제 설명

민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.

그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는 지나가던 행인들이 흘리고 간 금품들이 떨어져 있어, 그 길을 지나게 되면 일정한 양의 금품을 획득하게 된다. 한 번 지나간 길을 다시 방문하더라도 금품을 갈취당하거나 획득한다.

골목길의 연결 상태와, 각 골목길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이 주어졌을 때, 민승이가 최대한 유리한 경로를 따라 집에서 코레스코 콘도까지 가기 위해서는 어떻게 해야 하는지 출력하는 프로그램을 작성하시오. 

보유 중인 금품의 양이 음수가 될 수 있다. 최대한 유리한 경로 또는 최적의 경로는 민승이네 집에서 출발하여 코레스코 콘도에 도착하는 경로 중 금품의 양이 최대가 되는 경로이다. 

입력

첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어진다. 이는 u번 교차점에서 v번 교차점으로 이동할 수 있는 골목길이 나있다는 의미이다. 즉, 주어지는 골목길들은 기본적으로 모두 일방통행로이다. w (0 ≤ |w| ≤ 1,000)는 이 길을 지날 때 갈취당하거나 획득하게 되는 금품의 양이다. 음수는 갈취, 양수는 획득을 뜻한다.

골목길의 교차점 번호는 1이상 n이하의 정수이다. 민승이네 집은 1번 교차점에 있고, 이곳 코레스코 콘도는 n번 교차점에 있다.

출력

최적의 경로를 구할 수 있다면 민승이네 집부터 코레스코 콘도까지 가는 동안 거치게 되는 교차점들의 번호를 공백 하나를 사이에 두고 차례로 출력하면 된다. 그런데, 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생한다. 어떠한 경우에 그런 상황이 발생하는지 생각해 보자. 그러한 경우에는 -1을 출력하도록 한다.

최적의 경로가 여러 개 존재할 때는 아무거나 출력해도 된다.

 

2. 어떻게 풀까

  • 최단 경로 알고리즘을 이용해서 해결 할 수 있다.
  • 이 문제의 경우 최솟값을 구하는게 아니라 최댓값을 구하는 것이므로 음수 사이클을 찾는 것이 아니라 양수 사이클을 찾아야 한다.
  • 사이클이 형성되는지 확인 해야하므로 벨만 포드 알고리즘을 이용하여 해결했다.
    • 사이클이 존재하더라도 사이클이 목적지에 영향을 주지 않는다면 상관없다.
      • 이 점을 간과해서 틀렸다. ㅜ

 

3. 코드 (Java)

package baekjoon.shortest_path.골목길_20220318;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
  private static StringTokenizer tokenizer;

  private static int vertexCount;
  private static int edgeCount;
  private static int[][] edges;
  private static int[] distanceFromSource;
  private static int[] predecessor;

  public static void main(String[] args) throws IOException {
    tokenizer = new StringTokenizer(READER.readLine());
    vertexCount = Integer.parseInt(tokenizer.nextToken());
    edgeCount = Integer.parseInt(tokenizer.nextToken());

    init();
    bellmanFord();

    if (distanceFromSource[vertexCount] == Integer.MIN_VALUE) {
      System.out.println(-1);
      return;
    }

    for (int[] edge : edges) {
      int from = edge[0];
      int to = edge[1];
      int weight = edge[2];
      if (distanceFromSource[from] == Integer.MIN_VALUE) {
        continue;
      }

      if (isCycle(from, to, weight) && isCycleOnPath(to)) {
        System.out.println(-1);
        return;
      }
    }

    printShortestPath();
  }

  private static void init() throws IOException {
    edges = new int[edgeCount][];
    for (int i = 0; i < edgeCount; i++) {
      tokenizer = new StringTokenizer(READER.readLine());
      int from = Integer.parseInt(tokenizer.nextToken());
      int to = Integer.parseInt(tokenizer.nextToken());
      int weight = Integer.parseInt(tokenizer.nextToken());

      edges[i] = new int[]{from, to, weight};
    }

    distanceFromSource = new int[vertexCount + 1];
    predecessor = new int[vertexCount + 1];
    for (int i = 1; i <= vertexCount; i++) {
      distanceFromSource[i] = Integer.MIN_VALUE;
      predecessor[i] = -1;
    }
    distanceFromSource[1] = 0;
  }

  private static void bellmanFord() {
    for (int i = 0; i < vertexCount - 1; i++) {
      for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];
        int weight = edge[2];
        if (distanceFromSource[from] == Integer.MIN_VALUE) {
          continue;
        }
        if (distanceFromSource[to] < distanceFromSource[from] + weight) {
          distanceFromSource[to] = distanceFromSource[from] + weight;
          predecessor[to] = from;
        }
      }
    }
  }

  private static boolean isCycle(int from, int to, int weight) {
    return distanceFromSource[to] < distanceFromSource[from] + weight;
  }

  private static boolean isCycleOnPath(int targetVertex) {
    boolean[] visit = new boolean[vertexCount + 1];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(targetVertex);

    while (!queue.isEmpty()) {
      int currentVertex = queue.poll();
      if (visit[currentVertex]) {
        continue;
      }
      visit[currentVertex] = true;

      for (int[] edge : edges) {
        int from = edge[0];
        int to = edge[1];

        if (from == currentVertex && !visit[to]) {
          queue.add(to);
        }
      }
    }

    return visit[vertexCount];
  }

  private static void printShortestPath() {
    StringBuilder sb = new StringBuilder();
    int index = vertexCount;
    sb.append(vertexCount);
    while (predecessor[index] != -1) {
      sb.insert(0, predecessor[index] + " ");
      index = predecessor[index];
    }
    System.out.print(sb.toString());
  }
}
  • bellmanFord() 메소드를 통해 출발 노드부터 목적지 노드까지의 최단 경로를 구했다.
  • 목적지 노드까지의 경로가 없거나, 경로상에 양수 사이클이 존재할 경우 -1를 출력하도록 했다.
  • 경로 상에 양수 사이클이 존재하는지 검사했다.
    • 사이클이 존재하는 지 검증
      • 벨만 포드 알고리즘 이후에도 distanceFromSource가 갱신이 되는지 확인했다.
    • 사이클이 존재하고, 그 사이클이 경로상에 존재하는지 검증
      • 사이클이 존재하는 노드에서 목적지 노드까지의 경로가 있는지 BFS를 이용하여 확인했다.
      • 이 부분을 간과해서 틀렸다.
  • predecessor과 backtracking을 이용해서 최단 경로를 출력했다.
    • 처음에는 StringBuilder에 append()로 하나씩 추가한 후 reverse()로 마무리를 했었는데 계속 실패가 나와서 insert()로 바꾸었다.

 

벨만 포드 알고리즘을 알고 있다면 쉽게 풀 수 있긴 한데, 음수(문제는 양수)사이클이 출발 노드에서 목적지 노드까지의 경로에 포함되는지 검사하는 로직이 반드시 필요하다는것을 간과했다. 

'Coding Test > 백준' 카테고리의 다른 글

[백준] 1944. 복제 로봇 (Java)  (0) 2022.01.20
백준 - 1238 - 파티 (java)  (0) 2021.05.26
백준 - 16398 - 행성 연결 (java)  (0) 2021.05.25
백준 - 14502번 - 연구소 (java)  (0) 2021.05.25

+ Recent posts