그래프 최단 거리 구하는 알고리즘

1. 다익스트라(Dijkstra)
2. 벨만-포드(Bellman-Ford)
3. 플로이드-와샬(Floyd-Wrasahll)

벨만-포드 알고리즘이란?

---

벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

• 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다. 단, 음의 사이클은 없어야 한다.
• 시간 복잡도: O(mn)
  • n: 정점, m: 간선

	다익스트라	벨만-포드
음수 가중치	X	O
음수 사이클	X	X
시간 복잡도	O(mlogn)	O(mn)

동작 과정

---

• 매 단계마다 모든 간선을 전부 확인하면서 모든 노드 간의 최단 거리를 구해간다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정(n(정점)-1)번 반복한다.
   • 모든 간선 m개를 하나씩 확인한다.
   • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
4. 만약, 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 한 번 더 수행한다.
   -> 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

예시)

• 정점의 개수(n) = 5
• n = 1~5까지 간선을 모두 살펴보며 dist를 업데이트 한다.
• 간선의 개수(m) = 9
• 출발 정점 4

1) n = 1

• dist의 배열에서 무한이 아닌 값은 4이다. v = 4인 정점만 살펴본다. w = 1, 5와 연결되어 있다.
  

• dist[4] = 0 이고,

  • dist[1] = 8 이 된다.
    ① 현재, dist[1] = 무한
    ② dist[4] + cost(4, 1) = 0 + 8 = 8
    ① > ② 이므로 값 갱신
  • dist[5] = 3
    ① dist[5] = 무한
    ② dist[4] + cost(4, 5) = 0 + 3 = 3
    ① > ② 이므로 값 갱신

2) n = 2

• dist의 배열에 무한이 아닌 값은 1, 4, 5이다. v = 1, 4, 5인 간선만 본다.

• dist[4] = 0 갱신 x
• dist[1] = 8 이고
  • dist[2] = 18 이 된다.
    ① dist[2] = 무한
    ② dist[1] + cost(1, 2) = 8 + 10 = 18
    ① > ② 이므로 값 갱신
  • dist[3] = 5
    ① dist[3] = 무한
    ② dist[1] + cost(1, 3) = 8 + 5 = 13
    ① > ② 이므로 값 갱신
• dist[5] = 2
  • dist[4] 갱신 x
    ① dist[4] = 0
    ② dist[5] + cost(5, 4) = 3 + 9 = 12
    ① < ② 이므로 값 갱신 x
  • dist[2] 갱신 x
    ① dist[2] = 18
    ② dist[5] + cost(5, 2) = 3 + 31 = 34
    ① > ② 이므로 값 갱신 x

3) n = 3

• dist의 배열에 무한인 값이 없으므로 모든 간선을 위의 방식대로 살펴본다. n = 5까지 반복한다.
  

4) 최종 모습

4) 음수 사이클 확인하기

• 위 그림처럼 음수 가중치가 포함된 사이클이 있으면 음수 사이클이 존재하는 것이다. 벨만-포드 알고리즘에서 정점 n개 만큼 반복하는 과정을 한 번 더 진행한다. 이 때 바뀌는 값이 있다면 음수 사이클이 존재하는 것이다.

벨만-포드 알고리즘 구현 - Java

---

// Edge 클래스. 그래프를 구현할 때 간선 정보를 리스트에 저장.
class Edge {
    int v; // 나가는 정점
    int w; // 들어오는 정점
    int cost;

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

public class Main {
    static ArrayList<Edge> graph;
    static final int INF = Integer.MAX_VALUE;

    //정점의 개수, 간선의 개수, 출발지
    public static boolean BellmanFord(int n, int m, int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        //정점의 개수(n)만큼 반복. 음수 간선 순환 체크 안하려면 n-1번 반복
        for (int i = 0; i < n; i++) {
            //간선의 개수만큼 반복
            for (int j = 0; j < m; j++) {
                Edge edge = graph.get(j); //현재 간선

                //현재 간선의 들어오는 정점(w)에 대해 비교
                if (dist[edge.v] != INF && dist[edge.w] > dist[edge.v] + edge.cost) {
                    dist[edge.w] = dist[edge.v] + edge.cost;

                    // n번째 라운드에서 값이 갱신된다면 음수 순환 존재
                    if(i == n - 1) {
                        System.out.println("음수 사이클 존재");
                        return false;
                    }
                }
            }
        }

        //출력
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == INF)
                System.out.print("INF ");
            else
                System.out.print(dist[i] + " ");
        }

        return true;
    }

    public static void main(String[] args) throws IOException {

        //그래프 입력받기
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // 정점의 개수, 간선의 개수
        int n = Integer.parseInt(bf.readLine());
        int m = Integer.parseInt(bf.readLine());

        graph = new ArrayList<>();

        StringTokenizer st;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(bf.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.add(new Edge(v, w, cost));
        }

        //벨만-포드 알고리즘 수행
        BellmanFord(n, m, 4);
    }
}