3 min to read

다익스트라 알고리즘

다익스트라 알고리즘에 대해 알아보자!

Imagem de capa

다익스트라 알고리즘은 그래프 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘입니다.

뭐든지 문제를 보고 한번 풀어보는게 가장 이해하기 쉽겠죠?

백준 1238번 파티

문제를 다시 한번 설명드리자면 단방향이며(1에서 2로 가는 길이 2에서 1로 가는 길이랑 같지 않다는거죠!) 각각의 집에서 한 번호의 집에 최단거리로 놀러가고 돌아오는 시간을 구해야합니다. 그 후에 가장 오래걸리는 시간을 출력하면 되는거죠.

코드와 함께 보시죠!


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int X=Integer.parseInt(st.nextToken());

		//배열에 들어가는 값이 1부터이니 +1씩 늘려줍니다.
		int[][] map=new int[N+1][N+1];

		//다익스트라는 초기값을 무한대로 설정해줍니다.
	    for (int i = 1; i <= N; i++)
	        for (int j = 1; j <= N; j++)
	            if (i != j)
	                map[i][j] = 9999999;

		for(int i=0;i<M;i++){
			st=new StringTokenizer(br.readLine());
			map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]=Integer.parseInt(st.nextToken());

		}

		//i부터 j까지 가는 길이 k를 거쳐서 가는게 더 빠르다면 그 값으로 교체해줍니다.
		for(int k=1;k<=N;k++){
			for(int i=1;i<=N;i++){
				for(int j=1;j<=N;j++){
					if(map[i][j]>map[i][k]+map[k][j]){
						map[i][j]=map[i][k]+map[k][j];
					}
				}
			}
		}
        //각각의 집에서 x에 가고 돌아오는 길을 더해 가장 오래 걸리는 시간을 구해줍니다.
		int max=0;
		for (int i = 1; i <=N; i++){
	        int tmp = map[X][i];
	        int tmp2 = map[i][X];

	        if (max < tmp2 + tmp)
	            max = tmp2 + tmp;
	    }
	    System.out.println(max);
    }

}