Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?

Java / Python

4. 타임머신

11657번

벨만 포드 알고리즘을 배우는 문제

이번 문제는 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하는 문제입니다.
벨만 포드 알고리즘을 이용합니다.

• Java

import java.io.*;
import java.util.*;

class Bus{
	int start, end, weight;

	public Bus(int start, int end, int weight){
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
}

public class Main {
	static final int INF = 100000000;
	static int N, M;
	static int start, g, h;
	static long[] dist; 
	static ArrayList<Bus> busarr = new ArrayList<Bus>();
    
	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()); 
        
		N = Integer.parseInt(st.nextToken());			
		M = Integer.parseInt(st.nextToken());
        
		dist = new long[N + 1];

		Arrays.fill(dist,INF);
        
		for(int i = 0; i < M; i++){    
			// 입력값 초기화
			st = new StringTokenizer(br.readLine()); 
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());			
			int time = Integer.parseInt(st.nextToken());
            
			busarr.add(new Bus(start, end, time));
		}
		if(bellmanFord(1)) {
			bw.write(-1 + "\n");
		}else {
			for(int i=2; i <= N; i++) {
				if(dist[i] == INF)
					bw.write(-1 + "\n");
				else{
					bw.write(dist[i] +  "\n");
				}
			}    
		}
		bw.flush();
		bw.close();
		br.close();
	}

	public static boolean bellmanFord(int start) { 
		boolean cycle = false;
		dist[start] = 0;
        
		// 간선의 수 만큼 순회
		for(int i=0; i <= N; i++) {
			for(int j=0; j < M; j++) {
				int s = busarr.get(j).start;
				int e = busarr.get(j).end;
				int w = busarr.get(j).weight;
                
				// 시작점 최단경로가 무한대가 아닐 경우, 
				// 시작점 최단경로 + 목적지까지 가중치가 목적지 최단경로보다 작을때  
				if(dist[s] != INF && dist[s] + w < dist[e]) {
					dist[e] = dist[s] + w;
					if(i == N)
						cycle = true;
				}
			}
		}
		// 음의 사이클 점검
		return cycle;
	}
}

• Python

import sys
 
def bellmanFord():
    global isPossible
 
    for repeat in range(N):
        for i in range(1, N+1):
            for weight, vec in busarr[i]:
                if dist[i] != INF and dist[vec] > dist[i] + weight:
                    dist[vec] = dist[i] + weight
                    if repeat == N-1:
                        isPossible = False

N, M = map(int,sys.stdin.readline().split())
busarr = [[] for _ in range(N+1)]
INF = 10000000000
dist = [INF] * (N+1)
dist[1] = 0
isPossible = True
 
for _ in range(M):
    a,b,c = map(int,sys.stdin.readline().split())
    busarr[a].append((c,b))

bellmanFord()

if not isPossible:
    print(-1)
else:
    for d in dist[2:]:
        print(d if d !=INF else -1)