Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

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

Java / Python

1. 최단경로

1753번

다익스트라 알고리즘을 배우는 문제

이번 문제는 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하는 문제입니다. (단, 모든 간선의 가중치는 10 이하의 자연수)
다익스트라 알고리즘(Dijkstra Algorithm)을 이용합니다.

• Java

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

class Node implements Comparable<Node>{
	int end, weight;

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

	@Override
	public int compareTo(Node o) {
		return weight - o.weight;
	}
}

public class Main {
	static int V, E, K;
	static LinkedList<Node>[] graph;
	static int[] dist;
	static boolean[] visit;
    
	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()); 
        
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine());
        
		visit = new boolean[V+1];
		graph = new LinkedList[V+1];
		dist = new int[V+1];
		Arrays.fill(dist, -1);
        
		for(int i = 1; i <= V; i++)
			graph[i] = new LinkedList<>();
        
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());            
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			graph[v1].add(new Node(v2, w));
		}
            
		dijkstra(K);
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= V; i++)
			sb.append(dist[i] == -1 ? "INF" : dist[i]).append("\n");
			
		bw.write(sb.toString() + "\n");
    
		bw.flush();
		bw.close();
		br.close();
	}

	public static void dijkstra(int start) { 
		PriorityQueue<Node> pqueue = new PriorityQueue<>();
		pqueue.offer(new Node(start, 0));
		dist[start] = 0;

		while (!pqueue.isEmpty()) {
			Node now = pqueue.poll();
            
			if(!visit[now.end]){
				visit[now.end] = true;
				for (Node next : graph[now.end]) {
					if(dist[next.end] == -1 || dist[next.end] > dist[now.end] + next.weight){
						dist[next.end] = dist[now.end] + next.weight;            
						pqueue.offer(new Node(next.end, dist[next.end]));
					}                             
				}                
			}
		}
	}
}

• Python

from heapq import heappush, heappop
import sys
inf = 100000000
V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())
graph = [[] for _ in range(V + 1)]
dp = [inf] * (V + 1)
heap = []

# dijkstra 경로 탐색
def dijkstra(start):
    dp[start] = 0
    heappush(heap, [0, start])
    while heap:
        w, n = heappop(heap)
        for new_n, wei in graph[n]:
            new_w = wei + w
            if new_w < dp[new_n]:
                dp[new_n] = new_w
                heappush(heap, [new_w, new_n])
                
                
for i in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([v, w])
dijkstra(K)
for i in dp[1:]:
    print(i if i != inf else "INF")