벨만 포드

전처리

static class Wrapper
{
    int[] dist;
    boolean is_cycle;
    Wrapper (int[] dist, boolean is_cycle) { this.dist = dist; this.is_cycle = is_cycle; }
}

static class Edge
{
    int u, v, w;
    Edge (int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
}

for (int i=0; i<M; i++)
{
    st = new StringTokenizer(input.readLine());

    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    int w = Integer.parseInt(st.nextToken());

    G.add( new Edge(u, v, w) );
}

 

 

 

 

벨만 포드

static Wrapper Bellman_Ford (ArrayList<Edge> G, int N, int INF)
{
    boolean is_cycle = false;
    int[] dist = new int[N+1];

    for (int i=1; i<=N; i++)
        dist[i] = INF;

    for (int i=0; i<N; i++)
    {
        for (int j=0; j<G.size(); j++)
        {
            int u = G.get(j).u;
            int v = G.get(j).v;
            int w = G.get(j).w;

            if ( dist[u] + w < dist[v] )
            {
                dist[v] = dist[u] + w;

                if ( i == N-1 )
                {
                    is_cycle = true;
                    break;
                }
            }
        }
    }
    return new Wrapper(dist, is_cycle);
}