最短パス

多学科の概念

最短パスアルゴリズム
(始点から全頂点の最短距離を求める)

潍坊向城

音重み付け不可(音の重み付けはValmanfordでなければならない)

from

と同様
MST:クルーズ、フリーム
->アクセント(方向なし)
最短パス:Daestra
->負の重み付け不可(有向)

例

に似ている
ダンダエストラ(これまでの費用+このノード接続費用VS元の費用)比較、minに更新

ろんり

つながっている(選ばれた)子供たちの腕が触れる(隣接する)子供の中で
開始ノードに最も近い子を選択

インプリメンテーションコード

Priority Queueバージョンの使用

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//백준 골드5 1753 최단경로
//PQ 다익스트라 연습
public class BJ_G5_1753_최단경로 {

	static class Edge implements Comparable<Edge>{
		int node, weight;
		public Edge(int node, int weight) {
			this.node = node;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			return weight-o.weight;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V =  Integer.parseInt(st.nextToken());
		int E =  Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(br.readLine()) - 1;
		int dist[] = new int[V]; //시작 정점부터 i번 정점까지의 최단거리
		Arrays.fill(dist, Integer.MAX_VALUE);
		ArrayList<ArrayList<Edge>> adjList = new ArrayList<>();
		for(int i=0; i<V; i++) adjList.add(new ArrayList<>());
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken())-1;
			int to = Integer.parseInt(st.nextToken())-1;
			int weight = Integer.parseInt(st.nextToken());
			adjList.get(from).add(new Edge(to, weight)); //유방향성
		}
		
		//pq는 시작노드->해당노드까지의 거리를 담는다
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] v = new boolean[V];
		pq.add(new Edge(K, 0));
		dist[K] = 0;	
		while(!pq.isEmpty()) {
			//시작노드부터 거리가 가장 가까운 애 poll	
			Edge curr = pq.poll();
			
			//일단 뽑히면 가장 가까운 거리로 온거니까 그다음 부턴 얘를 다시 살펴볼 필요가 없음
            if (v[curr.node]) continue;
            v[curr.node] = true;
            
            //다른 방법으로 간 경로가 더 가까울 수도 있으니 방문체크 X
			for(Edge e : adjList.get(curr.node)) {
				int d = dist[curr.node] + e.weight;
				//아직 확정(방문)되지 않은 애면, 현재 선 연결된 애들 중 기존 정보보다 저 가까운 애가 있으면 큐에 넣기
				if(d<dist[e.node]) {  
					//해당 노드부터 d까지의 거리 갱신
					dist[e.node] = d;
					//방문 안한 애일 수도 있으니 pq에 넣음
					pq.add(new Edge(e.node, d));
				}
			}
		}
		for(int d : dist) System.out.println(d!=Integer.MAX_VALUE?d:"INF");
	}
}

適用例

写真を適用

関連する問題

プラチナ51753最短経路