벨만-포드

• 벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

  • 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색

  • 음수 가중치 에지가 있어도 수행할 수 있음

  • 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음

  • O(VE) (노드 수 : V, 에지 수 : E)

타임머신으로 빨리 가기

Question - 11657

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N59_P11657_타임머신으로_빨리가기 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int node, edge;

    static long[] distance;
    static cEdge edges[];

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        distance = new long[node + 1];
        edges = new cEdge[edge + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);

        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            edges[i] = new cEdge(start, end, time);
        }

        // bellman-ford-moore
        distance[1] = 0;
        for (int i = 1; i < node; i++) { // node보다 1개 적은 수만큼 반
            for (int j = 0; j < edge; j++) {
                cEdge now = edges[j]; //here
                if (distance[now.start] != Integer.MAX_VALUE
                        && distance[now.end] > distance[now.start] + now.time) {
                    distance[now.end] = distance[now.start] + now.time;
                }
            }
        }

        boolean mCycle = false;
        for (int i = 0; i < edge; i++) {
            cEdge now = edges[i];
            if (distance[now.start] != Integer.MAX_VALUE
                    && distance[now.end] > distance[now.start] + now.time) {
                mCycle = true;
            }
        }

        if (!mCycle) {
            for (int i = 2; i <= node; i++) {
                if (distance[i] == Integer.MAX_VALUE)
                    System.out.println("-1");
                else
                    System.out.println(distance[i]);
            }
        } else {
            System.out.println("-1");
        }
    }
}

class cEdge {
    int start, end, time;
    public cEdge(int start, int end, int time) {
         this.start = start;
         this.end = end;
         this.time = time;
    }
}

Insight

Idea

reference

세일즈맨의 고민

Question - 1219

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N60_P1219_세일즈맨의_고민 {

    static int node, veryStart, veryEnd, edge;

    static long[] earning;
    static long[] distance;

    static mEdge[] edgeList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        node = Integer.parseInt(st.nextToken());
        veryStart = Integer.parseInt(st.nextToken());
        veryEnd = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        edgeList = new mEdge[edge];
        earning = new long[node]; // 각 도시에서 벌 수 있는 돈
        distance = new long[node];
        Arrays.fill(distance, Long.MIN_VALUE);

        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edgeList[i] = new mEdge(s, e, c);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < node; i++) {
            earning[i] = Long.parseLong(st.nextToken());
        }

        // 변형된 벨만 포드
        distance[veryStart] = earning[veryStart];

        for (int i = 0; i <= node + 100; i++) {
            for (int j = 0; j < edge; j++) {
                int start = edgeList[j].start;
                int end = edgeList[j].end;
                int cost = edgeList[j].cost;

                // 출발 노드가 방문하지 않은 노드 skip
                if (distance[start] == Long.MIN_VALUE) continue;

                // 출발 노드가 양수 사이클에 연결되 노드라면 동료 노드도 연결 노드로 업데이트
                else if (distance[start] == Long.MAX_VALUE)
                    distance[end] = Long.MAX_VALUE;

                // 더 많은 돈을 벌 수 있는 새로운 경로 발견됐을 때 새로운 경로값으로 업데이트
                else if (distance[end] < distance[start] + earning[end] - cost) {
                    distance[end] = distance[start] + earning[end] -cost;
                    if (i >= node -1) distance[end] = Long.MAX_VALUE;
                }
            }
        }

        // 도착 불가능
        if (distance[veryEnd] == Long.MIN_VALUE) System.out.println("gg");

        // 양수 사이클 연결돼 무한대 돈을 벌수 있을 때
        else if (distance[veryEnd] == Long.MAX_VALUE) System.out.println("Gee");

        // 이외
        else System.out.println(distance[veryEnd]);
    }
}

class mEdge {
    int start, end, cost;
    public mEdge(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
}

Insight

Idea

• 그래프 이론

• 그래프 탐색

• 벨만-포드

reference