[伯俊]1404号フロイド/Java,Python


Baekjoon Online Judge


algorithm practice


-問題を逐次解く


25.最短経路


図形の幹線に重みがない場合は、BFSを使用して最短距離を検索できます.重みがあればどうなりますか?
Java/Python

5.フロイド


11404号
FloydとShellアルゴリズムの問題を学ぶ

これは、AからBまでのコストの最大値を求めることができるすべての都市ペア(A、B)に関するプログラムです.
floodとshallアルゴリズムを使用!
  • Java
  • import java.io.*;
    import java.util.*;
    
    public class Main {
    	static final int INF = 1000000000;
    	static int[][] dist; 
    	static int cityCnt;
        
    	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 = null;
            
    		cityCnt = Integer.parseInt(br.readLine());			
    		int busCnt = Integer.parseInt(br.readLine());
            
    		dist = new int[cityCnt + 1][cityCnt + 1];
    
    		for(int i = 1; i <= cityCnt; i++){
    			for(int j = 1; j <= cityCnt; j++){
    				if(i != j) dist[i][j] = INF;
    			}
    		}
            
    		while(busCnt-- > 0){    
    			// 입력값 초기화
    			st = new StringTokenizer(br.readLine()); 
                
    			int start = Integer.parseInt(st.nextToken());
    			int end = Integer.parseInt(st.nextToken());			
    			int time = Integer.parseInt(st.nextToken());
                
    			dist[start][end] = Math.min(dist[start][end], time);
    		}
    		floydWarshall();
            
    		StringBuilder sb = new StringBuilder();
    		for(int i=1; i <= cityCnt; i++) {
    			for(int j=1; j <= cityCnt; j++) {
    				if(dist[i][j] >= INF) sb.append("0 ");
    				else sb.append(dist[i][j] + " ");
    			}
    			sb.append("\n");
    		}
            
    		bw.write(sb.toString());
            
    		bw.flush();
    		bw.close();
    		br.close();
    	}
    
    	public static void floydWarshall() { 
    		// 기준 K
    		for(int k = 1; k <= cityCnt; k++) {
    			// 출발 노드 i
    			for(int i = 1; i <= cityCnt; i++) {
    				// 도착 노드 j
    				for(int j = 1; j <= cityCnt; j++) {
    					//i -> k , k -> j 가는 거리, i -> j 가는 거리를 비교 (작은 값 : 최소거리)
    					dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
    				}
    			}
    		}
    	}
    }
  • Python
  • import sys
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    INF = 10000000000
    city = [[INF] * N for i in range(N)]
    
    for i in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        if city[a - 1][b - 1] > c:
            city[a - 1][b - 1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j and city[i][j] > city[i][k] + city[k][j]:
                    city[i][j] = city[i][k] + city[k][j]
    for i in city:
        for j in i:
            if j == INF:
                print(0, end=' ')
            else:
                print(j, end=' ')
        print()