[BOJ] 최단경로(with Java, C++ code)::알고리즘

문제 출처 : BOJ(https://www.acmicpc.net/problem/1753)

 

 

 보통 그래프에서 정점끼리의 최단경로를 구하는 문제는 4가지가 있습니다.

 

1) 하나의 정점에서 다른 하나의 정점까지의 최단경로를 구하는 문제

2) 하나의 정점에서 모든 정점까지의 최단경로를 구하는 문제(다익스트라 알고리즘)

3) 모든 정점에서 하나의 정점까지의 최단경로를 구하는 문제

4) 모든 정점에서 모든 정점까지의 최단경로를 구하는 문제(플로이드 와샬 알고리즘)

 

 추가로 모든 정점을 최소비용으로 연결하는 문제(MST: Minimum Spanning Tree, 최소 신장 트리)는 2가지가 있습니다.

 

5) 모든 정점까지의 최소비용을 오름차순으로 정렬해 연결하는 문제(크루스칼 알고리즘)

6) 하나의 정점에서 모든 정점까지 단계적으로 확장해 연결하는 문제(프림 알고리즘)

 

 

 해당 문제는 시작 정점이 주어지고, 모든 정점까지의 최단경로를 구하는 그래프 문제로 2번에 해당합니다.

 따라서 다익스트라((Dijkstra) 알고리즘을 이용해서 해결할 수 있습니다.

 

정점의 개수 : V

간선의 개수 : E

시작 정점 : K

 

 셋째 줄부터 E개의 줄에 걸쳐 각 간선의 정보가 주어집니다.

< u에서 v로 가는 가중치 w >

---

 우선, 시작 정점에서 모든 정점까지의 거리를 최대값으로 초기화합니다.

 시작 정점에서 시작 정점으로 가는 방법은 없기 때문에 0으로 초기화합니다.

 

 모든 간선의 정보를 배열에 저장합니다.

 

 이후 우선순위 큐를 이용해 간선의 거리를 오름차순으로 정렬하고, 시작 정점부터 최단경로를 찾아갑니다.

 

 

Java 코드

 

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

class Node {
	int next, weight;
	
	Node(int next, int weight) {
		this.next = next;
		this.weight = weight;
	}
}

public class Main_1753_최단경로_List {

	public static int INF = 987654321;
	public static int ans, V, E, K;
	
	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().trim());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine().trim());
		
		int[] dist = new int[V + 1];
		Arrays.fill(dist, INF);
		
		@SuppressWarnings("unchecked")
		List<Node>[] lines = new List[V + 1];
		for (int i = 1; i <= V; ++i)
			lines[i] = new ArrayList<Node>();
		
		for (int i = 0; i < E; ++i) {
			st = new StringTokenizer(br.readLine().trim());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			lines[u].add(new Node(v, w));
		}
		
		Queue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.weight - n2.weight);
		dist[K] = 0;
		pq.add(new Node(K, 0));
		
		while (!pq.isEmpty()) {
			Node node = pq.poll();
			
			for (Node next : lines[node.next]) {
				if (dist[next.next] > dist[node.next] + next.weight) {
					dist[next.next] = dist[node.next] + next.weight;
					pq.add(new Node(next.next, dist[next.next]));
				}
			}
		}
		
		for (int i = 1; i <= V; ++i)
			bw.write(dist[i] == INF ? "INF\n" : dist[i] + "\n");
		
		bw.flush();
		bw.close();
		br.close();
	}

}

 

C++ 코드

 

#include <iostream>
#include <vector>
#include <queue>

#define endl    '\n'
#define INF     987654321
#define MAX     20010

using namespace std;

struct node
{
    int next, weight;

    bool operator<(const node& r) const
    {
        return r.weight < weight;
    }
};

int ans, V, E, K;
int dist[MAX];
bool visit[MAX];
vector<pair<int, int>> vec[MAX];
priority_queue<node> pq;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> V >> E >> K;

    fill(dist + 1, dist + V + 1, INF);
    dist[K] = 0;

    for (int i = 0; i < E; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        vec[u].push_back({ v, w });
    }

    pq.push({ K, 0 });

    while (!pq.empty())
    {
        int next = pq.top().next;
        int weight = pq.top().weight;
        pq.pop();

        if (visit[next])
            continue;

        visit[next] = true;

        for (auto next_node : vec[next])
        {
            if (dist[next] + next_node.second < dist[next_node.first])
            {
                dist[next_node.first] = dist[next] + next_node.second;
                pq.push({ next_node.first, dist[next_node.first] });
            }
        }
    }

    for (int i = 1; i <= V; ++i)
    {
        if (dist[i] == INF)
            cout << "INF" << endl;
        else
            cout << dist[i] << endl;
    }
}

 

결과

 

0
2
3
7
INF