다 익스트라 경로 출력 Java - da igseuteula gyeonglo chullyeog Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

import java.io.*;

import java.util.*;

public class Main {

static final int INF=987654321; // 충분히 큰 값 (무한대)

static int N,E;

static int[][] Graph;

static int[] Dist;

public static void main(String[] args) throws IOException {

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st=new StringTokenizer(br.readLine());

N=Integer.parseInt(st.nextToken()); // 노드의 개수

E=Integer.parseInt(st.nextToken()); // 간선의 개수

Graph=new int[N][N];

Dist=new int[N];

for(int i=0;i<N;i++){

for(int j=0;j<N;j++){

if(i==j) Graph[i][j]=0;

else Graph[i][j]=INF;

}

}

for(int i=0;i<E;i++){

st=new StringTokenizer(br.readLine());

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

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

int cost=Integer.parseInt(st.nextToken());

Graph[u][v]=Graph[v][u]=cost;

}

dijkstra(0);

for(int i=0;i<N;i++){

System.out.print(Dist[i]+" ");

}

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

public static void dijkstra(int start){

PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);

boolean[] visited=new boolean[N+1];

for(int i=0;i<N;i++){

Dist[i]=INF;

}

Dist[start]=0;

pq.add(new int[]{0,start});

while (!pq.isEmpty()){

int curr[]=pq.poll();

int u=curr[1];

if(visited[u]) continue;

visited[u]=true;

for(int v=0;v<N;v++){

if(Dist[v]>Dist[u]+Graph[u][v]){

Dist[v]=Dist[u]+Graph[u][v];

pq.add(new int[]{Dist[v],v});

}

}

}

}