학습목표
- Kruskal 최소신장트리(MST) 알고리즘을 구현할 수 있다.
- Prim 최소신장트리(MST) 알고리즘을 구현할 수 있다.
- 다익스트라 최단경로 알고리즘을 구현할 수 있다.
1. 최소신장트리(Minimum Spanning Tree) 알고리즘
트리 = 비선형 자료 구조
트리는 부모와 자식간의 관계밖에 표시가 안되는데 그래프는 다른 요소간의 관계도 표시할 수 있음 , 그래서 사이클이 만들어짐 이게 단점이 될 수도 있음
신장트리는 그래프에 최소한의 간선만 사용하여 전체 정점으로 연결하는 트리이다. 아래 그림에서 그래프 (b), (c), (d)는 그래프 (a)의 신장트리이다.
연결을 하는데 간선을 최소로 하는 것
최소 간선 : 노드 개수 - 1
최소 간선을 사용하는 이유 : 오버헤드(비용) 문제를 해결 할 수 있다.
최소신장트리는 가중치가 설정된 그래프에서 간선의 가중치들의 합이 가장 작은 부분 그래프(신장트리)를 의미한다. 각 정점들을 간선으로 연결하는 동시에, 가장 적은 비용을 들여서 연결을 해야 한다. 즉, 간선에 비용이 부여되어 있는데 그 중에서 가장 적은 비용이 발생하는 간선을 선택하는 것이다. 아래 그림은 가중치 그래프가 주어졌을 때 신장트리 중 최소비용으로 연결한 최소신장트리의 예시이다.
크루스칼 알고리즘
크루스칼 알고리즘은 각 단계에서 가중치가 작은 간선부터 선택한다. 선택하는 과정에서 사이클이 만들어질 경우 그 간선은 선택하지 않는다. 신장트리는 n 개의 정점을 가질 때, 반드시 n-1 개의 간선을 가지게 되어있으므로 선택 간선의 수가 n-1 개가 되면 종료한다.
크루스칼 알고리즘을 구현할 때는 다음과 같은 사항을 고려해야 한다:
- 가중치가 작은 간선을 선택하는 데는 많은 시간이 소요되므로 모든 간선을 미리 오름차순으로 정렬한다.
- 사이클이 만들어지는지 확인합니다. 방문한 정점을 또 방문했는지를 확인한다.
크루스칼 알고리즘은 하나의 트리를 유지하며 만들어지는 것이 아니라, 여러 개의 트리를 생성하면서 트리를 합치는 방법을 사용하기 때문에 임의의 정점이 선택되었을 때, 그 정점이 어느 집합의 원소인지를 알아내는 연산이 추가적으로 필요하다.
- init_set 연산 : 최초의 정점 하나를 원소로 가지는 집합을 초기화하는 연산
- find 연산 : 주어진 정점이 어느 집합의 원소인지를 알아내는 연산
- union 연산 : 두 집합을 하나의 집합으로 합치는 연산
크루스칼 알고리즘의 동작과정을 그림과 함께 설명한다.
정점, 간선, 가중치로 구성된 그래프가 입력으로 주어진다. 전처리로 간선을 가중치 값을 기준으로 오름차순 정렬한다.
0번과 5번을 합집합하고 Parent를 0번으로 설정하여 연결한다.
Parent가 바뀌면 Rank는 필요없다.
Rank는 일단 1, 다른게 해당 index에 연결이 되면 Rank가 + 1증감함
그 다음 가중치가 2번째로 작은 2번 3번이 선택되고 3번의 Parent를 2로 설정하고 2의 Rank를 1 증감시킴
3번의 Parent인 2로 가고 2의 Parent의 1이다. 6번의 Parent도 부모가 1이다. 만약 6과 3을 연결하면 사이클이 생김 - 그래서 18을 버림
같은 집합에서 간선을 선택을 하는 순간 사이클이 됨.
6번을 따라가보니까 1번이 부모네? , 3번도 따라가보니까 1번이 부모이다.
4와 6을 (24간선)연결하면 사이클이 생겨 버림
사이클이 만들어지면 둘 중에 누구를 버릴까? ⇒ 가중치가 높은거 부터 버린다.
그림으로는 사이클은 눈에 쉽게 보이지만 프로그래밍으로 구현을 할 때에는 사이클을 알아내기가 어렵다.
정리 :
크루스칼 알고리즘 우선 선택 - 가중치가 작은 간선 집합
각 각의 개별 집합을 Union(합집합)한다고 생각하면된다.
다음은 최소비용 신장트리를 만드는 크루스칼 알고리즘을 기술한 의사코드이다.
입력 : 가중치 그래프 $G = (V,E)$, n은 정점 개수 결과 : 최소신장트리를 이루는 간선 집합, $E_T$
kruskal (G)
E를 ≤ ... ≤ w(e_e)가 되도록 정렬한다.
E_T <- Ф; ecounter <- 0
k <- 0
while ecounter<(n-1) do
k-k+1
if ErU{e}가 사이클을 포함하지 않으면
then Er-ErU{e}; ecounter - ecounter +1
return Er
크루스칼 알고리즘에서 선택된 간선이 사이클을 형성하는지 파악하기 위해 집합 연산을 수행하는 find(), union() 메소드를 활용한다.
다음은 크루스칼 알고리즘을 자바로 구현한 예제이다.
package s240521;
import java.util.*;
class Graph { // Comparable 인터페이스를 사용한다는 의미는 크기 비교 가능한 객체
class Edge implements Comparable<Edge> { // 간선 클래스
int src, dest, weight; // 두 정점과 가중치
public int compareTo(Edge compareEdge) { // 가중치로 크기 비교
return this.weight - compareEdge.weight;
}
}
class subset { // union-find 연산에 사용되는 부분집합 클래스
int parent, rank;
public String toString() {
return String.format("P:%d,R:%d", parent, rank);
}
}
int V, E; // 정점 개수와 간선 개수
Edge edge[]; // 간선 객체 배열
Graph(int v, int e) { // 그래프 객체 생성자
V = v;
E = e;
edge = new Edge[E]; // 간선 객체 배열 생성
for (int i=0; i<e; ++i)
edge[i] = new Edge(); // 간선 객체 생성
}
int find(subset subsets[], int i) { // i 원소의 집합을 찾는 메소드
if (subsets[i].parent != i)
return find(subsets, subsets[i].parent);
else
return i;
}
void Union(subset subsets[], int xroot, int yroot) { // 두 집합을 union 연산하는 메소드
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
subsets[yroot].rank += subsets[xroot].rank;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
subsets[xroot].rank += subsets[yroot].rank;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank += subsets[yroot].rank;
}
}
void KruskalMST() { // 크루스칼 알고리즘을 구현하는 메인 메소드
Edge result[] = new Edge[V];
int e = 0, i = 0;
Arrays.sort(edge); // 간선 객체 배열을 오름차순 정렬
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset(); // 부분 집합 객체 생성
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 1;
}
// System.out.println(Arrays.toString(subsets));
i = 0;
while (e < V - 1) { // 간선의 수가 V-1 될 때까지 반복
Edge next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) { // 사이클을 만들지 않으면 간선 포함, 두 부분 집합 union
result[e++] = next_edge;
Union(subsets, x, y);
}
// System.out.println(Arrays.toString(subsets));
}
System.out.println("MST 간선 ");
for (i = 0; i < e; ++i) // MST에 포함되는 간선 출력
System.out.println(result[i].src+" -- "+result[i].dest+" == "+
result[i].weight);
}
public static void main (String[] args) {
int V = 7;
int E = 9;
Graph graph = new Graph(V, E);
// 간선 객체 초기화
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 28;
graph.edge[1].src = 0;
graph.edge[1].dest = 5;
graph.edge[1].weight = 10;
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 16;
graph.edge[3].src = 1;
graph.edge[3].dest = 6;
graph.edge[3].weight = 14;
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 12;
graph.edge[5].src = 3;
graph.edge[5].dest = 4;
graph.edge[5].weight = 22;
graph.edge[6].src = 3;
graph.edge[6].dest = 6;
graph.edge[6].weight = 18;
graph.edge[7].src = 4;
graph.edge[7].dest = 5;
graph.edge[7].weight = 25;
graph.edge[8].src = 4;
graph.edge[8].dest = 6;
graph.edge[8].weight = 24;
graph.KruskalMST();
}
}
프림 알고리즘(Prim’s algorithm)
프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 무방향 가중치 그래프가 주어졌을 때 최소신장트리를 찾는다. 하지만, 최소신장트리에 포함되는 간선을 선택하는 방법은 다르다.
프림 알고리즘이 최소신장트리를 찾는 개략적인 방법은 다음과 같다.
- 그래프에서 임의의 하나의 정점을 선택한다.
- 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하게 되는 정점을 선택한다.
- 1, 2 과정을 모든 정점이 선택될 때까지 반복한다.
크루스칼 알고리즘과 프림 알고리즘은 각각 장단점이 있으므로, 문제의 상황에 맞게 적절한 알고리즘을 선택하여 사용해야 한다.
알고리즘이 종료 후 만들어진 트리는 최소비용 신장트리를 만족한다.
프림 알고리즘의 동작 방식을 그림과 함께 설명한다.
Q[] 배열은 방문 여부를 표현함
0번이 최소신장트리에 포함되어야 함 만약 포함하지 않으면 Disconnect되어 버림, 그런데 10과 28중 어떤걸 선택해야하나? → 최소신장트리이기에 10(작은거) 부터 선택
0에서 나아갈려면 1,5 두 개의 정점 10과 28중에서 낮은 dist인 10을 사용하는게 더 최솟값
0과 5에서 가까운 1, 4중에 최소 비용인 4, 5(25)를 선택함
프림 알고리즘 : 방문된 정점에서 인접 된 가중치가 제일 작은 것만 연결해 나가는 것
최종 결과는 크루스칼 알고리즘과 같음
간선을 선택하는 순서가 다름
최소비용 신장트리를 만드는 프림 알고리즘 의사코드이다.
입력 : 가중치 그래프 $G = (V, E)$, s는 시작 정점 결과 : 최소신장트리를 이루는 정점들의 집합
Prim(G, s)
for each u ∈ V do
dist [u] <-∞
dist[s] <- 0
우선 순위큐 Q에 모든 정점을 삽입(우선순위는 dist[])
for i <- 0 to n-1 do
u <- delete_min(Q)
화면에 u를 출력
for each v ∈ (u의 인접 정점)
if(v ∈ Q and weight [u][v] < dist[v])
then dist[v] <- weight[u][v]
2. 최단경로 알고리즘
다익스트라(Dijkstra) 알고리즘 : 가중치 그래프와 시작 정점이 주어졌을 때, 시작 정점에서부터 각 정점까지의 최단 경로를 찾는 알고리즘
해당 사진은 무방향 가중치 그래프
각 정점에서 가장 거리가 작은 정점을 선택한다.
각 정점에서 가고하자는 각 정점까지 최단 경로로 갈 수 있도록 하는 문제
1까지 가는 최단거리는 확정이 되어 있다. 다이렉트로 가는 것이 경로를 거쳐서 가는것보다 최단 거리일 수 밖에 없음 4와 1 정점중에서 1을 사용할 수 있는 4와 1 정점 중에서 1이 최단경로임
1을 방문하는 순간 인접된 간선의 주변의 정점까지 갈 수 있는 최단 거리(dist)가 정해짐 → 업데이트
4를 방문하는 순간 기존에는 3의 최단거리가 10이 였는데 0→1→4→3 으로 (2+1+5 = 8) 으로 최단거리가 기존 보다 짧아져 업데이트(갱신)를 할 수 있음
어느걸 거쳐가는 것(경유)하는 것 보다 직선으로 가는것 (0→1→2) 이 가장 최단거리일수밖에 없다.
그리고 인접된 간선의 주변의 정점의 최단거리를 업데이트함
최단거리인 3을 방문하여 인접된 간선의 정점에 기존보다 더 최단거리로 갈 수 있는 5를 업데이트(갱신)한다
5에 방문하면 인접된 간선들의 정점인 6이 5를 거쳐가면 비용을 1 아낄 수 있기때문에 최단거리 업데이트
모든 정점이 방문으로 체크되면 알고리즘을 종료한다.
이때 dist[] 배열의 값은 시작정점에서 각 정점까지의 최단거리로 저장 된다. 다음은 다익스트라 알고리즘 의사코드이다.
입력: 가중치 그래프 G, 가중치는 음수가 아님
결과: distance 배열, distance[u]는 v에서 u까지의 최단거리
shortest_path(G, v)
S <- {v}
for 각 정점 w ∈ G do
distance[w] ←weight[v][w];
while 모든 정점이 S에 포함되지 않으면 do
u ← 집합 S에 속하지 않는 정점 중에서 최소 distance 정점;
S← S U{u}
for u에 인접하고 S에 있는 각 정점 z do
if distance [u]+weight[u][z] <distance [z]
then distance[z] ← distance [u]+weight [u] [z];
다익스트라 알고리즘을 자바로 구현한 예제이다.
package s240604;
import java.util.*;
public class DijkstraTest02 {
static int nV=7; // 정점 개수 : 7
static final int inf = 1000000; // 가중치 ∞ 값 설정
// 인접행렬로 표현된 가중치 그래프(입력)
static int[][] ad = { { 0, 2, inf, inf, 5, inf, inf },
{ 2, 0, 3, 8, 1, inf, inf },
{ inf, 3, 0, 1, inf, inf, 4 },
{ inf, 8, 1, 0, 5, 1, 5 },
{ 5, 1, inf, 5, 0, inf, inf },
{ inf, inf, inf, 1, inf, 0, 1 },
{ inf, inf, 4, 5, inf, 1, 0 } };
static int[] dist = new int[nV]; // 최단거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단경로 저장 배열
public static void shortestPath(int start){
dist[start] = 0;
for( int j = 0; j < nV; j++)
{
int min = inf+1;
int index = -1;
// 시작정점에서 거리가 가장 작은 정점의 인덱스 파악
for(int k = 0; k < nV; k++){
if(visit[k] == false && min > dist[k]){
min = dist[k];
index = k;
}
}
visit[index] = true;
// 최단거리, 경로 업데이트
for(int l = 0; l < nV; l++)
if(ad[index][l] != 0 && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l];
path[l] = index; // 경로 업데이트
}
}
// 시작정점에서 각 정점까지 최단거리 출력
System.out.print("dist[] : ");
for (int i = 0; i < nV; i++)
System.out.print(dist[i] + " ");
System.out.println();
// 시작정점에서 각 정점까지 최단경로 출력에 활용되는 path[] 배열 출력
System.out.print("path[] : ");
for (int i = 0; i < nV; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args) {
for (int i = 0; i < nV; i++)
dist[i] = inf;
shortestPath(0);
}
}
path[] : 는 해당하는 인덱스의 정점에 방문하기 위해 거쳐오는 마지막 정점을 포함하는 배열
다익스트라 알고리즘에서는 dist[] 배열이 시작정점에서 각 정점까지의 최단거리 값을 저장한다. 시작정점에서 각 정점까지의 경로를 출력하기 위해서는 path[] 배열을 활용할 수 있다. path[] 배열에는 dist[] 배열의 값이 갱신될 때 마지막에 경유(방문)하는 정점을 저장한다. 다익스트라 알고리즘 종료 후 path[] 배열에 저장된 값을 스택을 활용하여 역추적하면 각 정점까지의 최단경로(시작정점에서부터 경유하는 모든 정점)를 출력할 수 있다. 다익스트라 알고리즘의 시간 복잡도는 정점의 개수가 $n$일 때, 최단경로 계산 시 이중 루프를 활용하므로 $O(n_2)$ 이다.
추가 실습1) path 배열을 참조하여 최단 경로 출력
0 - 1 최단 경로 : 0 - 1
0 - 2 최단 경로 : 0 - 1 - 2
…
0 - 6 최단 경로 : 0 - 1 - 2 - 3 - 5 - 6
package s240604;
import java.util.*;
public class 추가실습1 {
static int nV = 7; // 정점 개수
static final int inf = 1000000; // 가중치 무한대 값 설정
// 인접 행렬로 표현된 가중치 그래프
static int[][] ad = {
{ 0, 2, inf, inf, 5, inf, inf }, // 정점 0의 간선들
{ 2, 0, 3, 8, 1, inf, inf }, // 정점 1의 간선들
{ inf, 3, 0, 1, inf, inf, 4 }, // 정점 2의 간선들
{ inf, 8, 1, 0, 5, 1, 5 }, // 정점 3의 간선들
{ 5, 1, inf, 5, 0, inf, inf }, // 정점 4의 간선들
{ inf, inf, inf, 1, inf, 0, 1 }, // 정점 5의 간선들
{ inf, inf, 4, 5, inf, 1, 0 } // 정점 6의 간선들
};
static int[] dist = new int[nV]; // 최단 거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단 경로 저장 배열
public static void shortestPath(int start) {
dist[start] = 0; // 시작 정점에서 자신까지의 거리는 0
for (int j = 0; j < nV; j++) { // 모든 정점에 대해 반복
int min = inf + 1;
int index = -1;
// 방문하지 않은 정점 중에서 가장 작은 거리를 가진 정점 찾기
for (int k = 0; k < nV; k++) {
if (!visit[k] && min > dist[k]) {
min = dist[k];
index = k;
}
}
if (index == -1) break; // 더 이상 접근할 수 없는 정점이 없으면 종료
visit[index] = true; // 해당 정점을 방문한 것으로 표시
// 인접한 정점들의 거리 갱신
for (int l = 0; l < nV; l++) {
if (ad[index][l] != inf && !visit[l] && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l]; // 거리 갱신
path[l] = index; // 경로 갱신
}
}
}
// 시작 정점에서 각 정점까지의 최단 경로 출력
for (int i = 0; i < nV; i++) {
System.out.print("0 - " + i + " 최단 경로 : ");
printPath(i);
System.out.println();
}
}
// 주어진 도착 정점까지의 경로를 출력하는 메서드
public static void printPath(int end) {
if (dist[end] == inf) { // 도착 정점이 접근 불가능한 경우
System.out.print("경로 없음"); // "경로 없음" 출력
return;
}
Stack<Integer> stack = new Stack<>(); // 경로를 저장할 스택
for (int at = end; at != -1; at = path[at]) { // 경로 배열을 역추적
stack.push(at); // 정점을 스택에 저장
}
// 스택에서 정점을 꺼내어 올바른 순서로 경로 출력
while (!stack.isEmpty()) {
System.out.print(stack.pop());
if (!stack.isEmpty()) System.out.print(" - ");
}
}
public static void main(String[] args) {
Arrays.fill(dist, inf); // 거리 배열을 무한대로 초기화
Arrays.fill(path, -1); // 경로 배열을 -1로 초기화 (경로 없음)
shortestPath(0); // 0번 정점에서 시작하는 최단 경로 계산
}
}
추가 실습2) 연습문제 5 해결
0 1 2 3 4 5 6
dist[] = 0 11 7 19 3 19 37
path[] = 0 0 4 4 0 2 5
0 - 6 최단 경로 : 0 - 4 - 2 - 5 - 6
package s240604;
import java.util.*;
/*
* 연습문제 5 해결
0 1 2 3 4 5 6
dist[] = 0 11 7 19 3 19 37
path[] = 0 0 4 4 0 2 5
* */
public class 추가실습2 {
static int nV = 7; // 정점 개수 : 7
static final int inf = 1000000; // 가중치 ∞ 값 설정
// 인접행렬로 표현된 가중치 그래프(입력)
static int[][] ad = { { 0, 11, 9, inf, 3, inf, inf },
{ 11, 0, inf, inf, 6, inf, 30 },
{ 9, inf, 0, inf, 19, 12, inf },
{ inf, inf, inf, 0, inf, inf, 21 },
{ inf, inf, 4, 16, 0, 21, 44 },
{ inf, inf, inf, inf, inf, 0, 18 },
{ inf, inf, inf, inf, inf, inf, inf } };
static int[] dist = new int[nV]; // 최단거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단경로 저장 배열
public static void shortestPath(int start){
dist[start] = 0;
for( int j = 0; j < nV; j++)
{
int min = inf+1;
int index = -1;
// 시작정점에서 거리가 가장 작은 정점의 인덱스 파악
for(int k = 0; k < nV; k++){
if(visit[k] == false && min > dist[k]){
min = dist[k];
index = k;
}
}
visit[index] = true;
// 최단거리, 경로 업데이트
for(int l = 0; l < nV; l++)
if(ad[index][l] != 0 && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l];
path[l] = index; // 경로 업데이트
}
}
// 시작정점에서 각 정점까지 최단거리 출력
System.out.print("dist[] : ");
for (int i = 0; i < nV; i++)
System.out.print(dist[i] + " ");
System.out.println();
// 시작정점에서 각 정점까지 최단경로 출력에 활용되는 path[] 배열 출력
System.out.print("path[] : ");
for (int i = 0; i < nV; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args) {
for (int i = 0; i < nV; i++)
dist[i] = inf;
shortestPath(0);
}
}
추가실습 3) 해당 문제 해결
0 1 2 3 4 5
dist[] = 0 @ @ @ @ @
dist[] = 0 7 9 @ @ 14
dist[] = 0 7 9 22 @ 14
dist[] = 0 7 9 20 @ 11
dist[] = 0 7 9 20 20 11
package s240604;
public class 추가실습3 {
static int nV = 6; // 정점 개수 : 7
static final int inf = 1000000; // 가중치 ∞ 값 설정
// 인접행렬로 표현된 가중치 그래프(입력)
static int[][] ad = { { 0, 7, 9, inf, inf, 14 }, // 0
{ 7, 0, 10, 15, inf, inf }, // 1
{ 9, 10, 0, 11, inf, 2 }, // 2
{ inf, 15, inf, 0, inf, 21}, // 3
{ inf, inf, inf, 6, 0, 9 }, // 4
{ 14, inf, 2, inf, 9, 0 }}; // 5
static int[] dist = new int[nV]; // 최단거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단경로 저장 배열
public static void shortestPath(int start){
dist[start] = 0;
for( int j = 0; j < nV; j++)
{
int min = inf+1;
int index = -1;
// 시작정점에서 거리가 가장 작은 정점의 인덱스 파악
for(int k = 0; k < nV; k++){
if(visit[k] == false && min > dist[k]){
min = dist[k];
index = k;
}
}
visit[index] = true;
// 최단거리, 경로 업데이트
for(int l = 0; l < nV; l++)
if(ad[index][l] != 0 && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l];
path[l] = index; // 경로 업데이트
}
}
// 시작정점에서 각 정점까지 최단거리 출력
System.out.print("dist[] : ");
for (int i = 0; i < nV; i++)
System.out.print(dist[i] + " ");
System.out.println();
// 시작정점에서 각 정점까지 최단경로 출력에 활용되는 path[] 배열 출력
System.out.print("path[] : ");
for (int i = 0; i < nV; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args) {
for (int i = 0; i < nV; i++)
dist[i] = inf;
shortestPath(0);
}
}학습목표
- Kruskal 최소신장트리(MST) 알고리즘을 구현할 수 있다.
- Prim 최소신장트리(MST) 알고리즘을 구현할 수 있다.
- 다익스트라 최단경로 알고리즘을 구현할 수 있다.
1. 최소신장트리(Minimum Spanning Tree) 알고리즘
트리 = 비선형 자료 구조
트리는 부모와 자식간의 관계밖에 표시가 안되는데 그래프는 다른 요소간의 관계도 표시할 수 있음 , 그래서 사이클이 만들어짐 이게 단점이 될 수도 있음
신장트리는 그래프에 최소한의 간선만 사용하여 전체 정점으로 연결하는 트리이다. 아래 그림에서 그래프 (b), (c), (d)는 그래프 (a)의 신장트리이다.
연결을 하는데 간선을 최소로 하는 것
최소 간선 : 노드 개수 - 1
최소 간선을 사용하는 이유 : 오버헤드(비용) 문제를 해결 할 수 있다.
최소신장트리는 가중치가 설정된 그래프에서 간선의 가중치들의 합이 가장 작은 부분 그래프(신장트리)를 의미한다. 각 정점들을 간선으로 연결하는 동시에, 가장 적은 비용을 들여서 연결을 해야 한다. 즉, 간선에 비용이 부여되어 있는데 그 중에서 가장 적은 비용이 발생하는 간선을 선택하는 것이다. 아래 그림은 가중치 그래프가 주어졌을 때 신장트리 중 최소비용으로 연결한 최소신장트리의 예시이다.
크루스칼 알고리즘
크루스칼 알고리즘은 각 단계에서 가중치가 작은 간선부터 선택한다. 선택하는 과정에서 사이클이 만들어질 경우 그 간선은 선택하지 않는다. 신장트리는 n 개의 정점을 가질 때, 반드시 n-1 개의 간선을 가지게 되어있으므로 선택 간선의 수가 n-1 개가 되면 종료한다.
크루스칼 알고리즘을 구현할 때는 다음과 같은 사항을 고려해야 한다:
- 가중치가 작은 간선을 선택하는 데는 많은 시간이 소요되므로 모든 간선을 미리 오름차순으로 정렬한다.
- 사이클이 만들어지는지 확인합니다. 방문한 정점을 또 방문했는지를 확인한다.
크루스칼 알고리즘은 하나의 트리를 유지하며 만들어지는 것이 아니라, 여러 개의 트리를 생성하면서 트리를 합치는 방법을 사용하기 때문에 임의의 정점이 선택되었을 때, 그 정점이 어느 집합의 원소인지를 알아내는 연산이 추가적으로 필요하다.
- init_set 연산 : 최초의 정점 하나를 원소로 가지는 집합을 초기화하는 연산
- find 연산 : 주어진 정점이 어느 집합의 원소인지를 알아내는 연산
- union 연산 : 두 집합을 하나의 집합으로 합치는 연산
크루스칼 알고리즘의 동작과정을 그림과 함께 설명한다.
정점, 간선, 가중치로 구성된 그래프가 입력으로 주어진다. 전처리로 간선을 가중치 값을 기준으로 오름차순 정렬한다.
0번과 5번을 합집합하고 Parent를 0번으로 설정하여 연결한다.
Parent가 바뀌면 Rank는 필요없다.
Rank는 일단 1, 다른게 해당 index에 연결이 되면 Rank가 + 1증감함
그 다음 가중치가 2번째로 작은 2번 3번이 선택되고 3번의 Parent를 2로 설정하고 2의 Rank를 1 증감시킴
3번의 Parent인 2로 가고 2의 Parent의 1이다. 6번의 Parent도 부모가 1이다. 만약 6과 3을 연결하면 사이클이 생김 - 그래서 18을 버림
같은 집합에서 간선을 선택을 하는 순간 사이클이 됨.
6번을 따라가보니까 1번이 부모네? , 3번도 따라가보니까 1번이 부모이다.
4와 6을 (24간선)연결하면 사이클이 생겨 버림
사이클이 만들어지면 둘 중에 누구를 버릴까? ⇒ 가중치가 높은거 부터 버린다.
그림으로는 사이클은 눈에 쉽게 보이지만 프로그래밍으로 구현을 할 때에는 사이클을 알아내기가 어렵다.
정리 :
크루스칼 알고리즘 우선 선택 - 가중치가 작은 간선 집합
각 각의 개별 집합을 Union(합집합)한다고 생각하면된다.
다음은 최소비용 신장트리를 만드는 크루스칼 알고리즘을 기술한 의사코드이다.
입력 : 가중치 그래프 , n은 정점 개수 결과 : 최소신장트리를 이루는 간선 집합,
kruskal (G)
E를 ≤ ... ≤ w(e_e)가 되도록 정렬한다.
E_T <- Ф; ecounter <- 0
k <- 0
while ecounter<(n-1) do
k-k+1
if ErU{e}가 사이클을 포함하지 않으면
then Er-ErU{e}; ecounter - ecounter +1
return Er
크루스칼 알고리즘에서 선택된 간선이 사이클을 형성하는지 파악하기 위해 집합 연산을 수행하는 find(), union() 메소드를 활용한다.
다음은 크루스칼 알고리즘을 자바로 구현한 예제이다.
package s240521;
import java.util.*;
class Graph { // Comparable 인터페이스를 사용한다는 의미는 크기 비교 가능한 객체
class Edge implements Comparable<Edge> { // 간선 클래스
int src, dest, weight; // 두 정점과 가중치
public int compareTo(Edge compareEdge) { // 가중치로 크기 비교
return this.weight - compareEdge.weight;
}
}
class subset { // union-find 연산에 사용되는 부분집합 클래스
int parent, rank;
public String toString() {
return String.format("P:%d,R:%d", parent, rank);
}
}
int V, E; // 정점 개수와 간선 개수
Edge edge[]; // 간선 객체 배열
Graph(int v, int e) { // 그래프 객체 생성자
V = v;
E = e;
edge = new Edge[E]; // 간선 객체 배열 생성
for (int i=0; i<e; ++i)
edge[i] = new Edge(); // 간선 객체 생성
}
int find(subset subsets[], int i) { // i 원소의 집합을 찾는 메소드
if (subsets[i].parent != i)
return find(subsets, subsets[i].parent);
else
return i;
}
void Union(subset subsets[], int xroot, int yroot) { // 두 집합을 union 연산하는 메소드
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
subsets[yroot].rank += subsets[xroot].rank;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
subsets[xroot].rank += subsets[yroot].rank;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank += subsets[yroot].rank;
}
}
void KruskalMST() { // 크루스칼 알고리즘을 구현하는 메인 메소드
Edge result[] = new Edge[V];
int e = 0, i = 0;
Arrays.sort(edge); // 간선 객체 배열을 오름차순 정렬
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset(); // 부분 집합 객체 생성
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 1;
}
// System.out.println(Arrays.toString(subsets));
i = 0;
while (e < V - 1) { // 간선의 수가 V-1 될 때까지 반복
Edge next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) { // 사이클을 만들지 않으면 간선 포함, 두 부분 집합 union
result[e++] = next_edge;
Union(subsets, x, y);
}
// System.out.println(Arrays.toString(subsets));
}
System.out.println("MST 간선 ");
for (i = 0; i < e; ++i) // MST에 포함되는 간선 출력
System.out.println(result[i].src+" -- "+result[i].dest+" == "+
result[i].weight);
}
public static void main (String[] args) {
int V = 7;
int E = 9;
Graph graph = new Graph(V, E);
// 간선 객체 초기화
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 28;
graph.edge[1].src = 0;
graph.edge[1].dest = 5;
graph.edge[1].weight = 10;
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 16;
graph.edge[3].src = 1;
graph.edge[3].dest = 6;
graph.edge[3].weight = 14;
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 12;
graph.edge[5].src = 3;
graph.edge[5].dest = 4;
graph.edge[5].weight = 22;
graph.edge[6].src = 3;
graph.edge[6].dest = 6;
graph.edge[6].weight = 18;
graph.edge[7].src = 4;
graph.edge[7].dest = 5;
graph.edge[7].weight = 25;
graph.edge[8].src = 4;
graph.edge[8].dest = 6;
graph.edge[8].weight = 24;
graph.KruskalMST();
}
}
프림 알고리즘(Prim’s algorithm)
프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 무방향 가중치 그래프가 주어졌을 때 최소신장트리를 찾는다. 하지만, 최소신장트리에 포함되는 간선을 선택하는 방법은 다르다.
프림 알고리즘이 최소신장트리를 찾는 개략적인 방법은 다음과 같다.
- 그래프에서 임의의 하나의 정점을 선택한다.
- 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하게 되는 정점을 선택한다.
- 1, 2 과정을 모든 정점이 선택될 때까지 반복한다.
크루스칼 알고리즘과 프림 알고리즘은 각각 장단점이 있으므로, 문제의 상황에 맞게 적절한 알고리즘을 선택하여 사용해야 한다.
알고리즘이 종료 후 만들어진 트리는 최소비용 신장트리를 만족한다.
프림 알고리즘의 동작 방식을 그림과 함께 설명한다.
Q[] 배열은 방문 여부를 표현함
0번이 최소신장트리에 포함되어야 함 만약 포함하지 않으면 Disconnect되어 버림, 그런데 10과 28중 어떤걸 선택해야하나? → 최소신장트리이기에 10(작은거) 부터 선택
0에서 나아갈려면 1,5 두 개의 정점 10과 28중에서 낮은 dist인 10을 사용하는게 더 최솟값
0과 5에서 가까운 1, 4중에 최소 비용인 4, 5(25)를 선택함
프림 알고리즘 : 방문된 정점에서 인접 된 가중치가 제일 작은 것만 연결해 나가는 것
최종 결과는 크루스칼 알고리즘과 같음
간선을 선택하는 순서가 다름
최소비용 신장트리를 만드는 프림 알고리즘 의사코드이다.
입력 : 가중치 그래프 , s는 시작 정점 결과 : 최소신장트리를 이루는 정점들의 집합
Prim(G, s)
for each u ∈ V do
dist [u] <-∞
dist[s] <- 0
우선 순위큐 Q에 모든 정점을 삽입(우선순위는 dist[])
for i <- 0 to n-1 do
u <- delete_min(Q)
화면에 u를 출력
for each v ∈ (u의 인접 정점)
if(v ∈ Q and weight [u][v] < dist[v])
then dist[v] <- weight[u][v]
2. 최단경로 알고리즘
다익스트라(Dijkstra) 알고리즘 : 가중치 그래프와 시작 정점이 주어졌을 때, 시작 정점에서부터 각 정점까지의 최단 경로를 찾는 알고리즘
해당 사진은 무방향 가중치 그래프
각 정점에서 가장 거리가 작은 정점을 선택한다.
각 정점에서 가고하자는 각 정점까지 최단 경로로 갈 수 있도록 하는 문제
1까지 가는 최단거리는 확정이 되어 있다. 다이렉트로 가는 것이 경로를 거쳐서 가는것보다 최단 거리일 수 밖에 없음 4와 1 정점중에서 1을 사용할 수 있는 4와 1 정점 중에서 1이 최단경로임
1을 방문하는 순간 인접된 간선의 주변의 정점까지 갈 수 있는 최단 거리(dist)가 정해짐 → 업데이트
4를 방문하는 순간 기존에는 3의 최단거리가 10이 였는데 0→1→4→3 으로 (2+1+5 = 8) 으로 최단거리가 기존 보다 짧아져 업데이트(갱신)를 할 수 있음
어느걸 거쳐가는 것(경유)하는 것 보다 직선으로 가는것 (0→1→2) 이 가장 최단거리일수밖에 없다.
그리고 인접된 간선의 주변의 정점의 최단거리를 업데이트함
최단거리인 3을 방문하여 인접된 간선의 정점에 기존보다 더 최단거리로 갈 수 있는 5를 업데이트(갱신)한다
5에 방문하면 인접된 간선들의 정점인 6이 5를 거쳐가면 비용을 1 아낄 수 있기때문에 최단거리 업데이트
모든 정점이 방문으로 체크되면 알고리즘을 종료한다.
이때 dist[] 배열의 값은 시작정점에서 각 정점까지의 최단거리로 저장 된다. 다음은 다익스트라 알고리즘 의사코드이다.
입력: 가중치 그래프 G, 가중치는 음수가 아님
결과: distance 배열, distance[u]는 v에서 u까지의 최단거리
shortest_path(G, v)
S <- {v}
for 각 정점 w ∈ G do
distance[w] ←weight[v][w];
while 모든 정점이 S에 포함되지 않으면 do
u ← 집합 S에 속하지 않는 정점 중에서 최소 distance 정점;
S← S U{u}
for u에 인접하고 S에 있는 각 정점 z do
if distance [u]+weight[u][z] <distance [z]
then distance[z] ← distance [u]+weight [u] [z];
다익스트라 알고리즘을 자바로 구현한 예제이다.
package s240604;
import java.util.*;
public class DijkstraTest02 {
static int nV=7; // 정점 개수 : 7
static final int inf = 1000000; // 가중치 ∞ 값 설정
// 인접행렬로 표현된 가중치 그래프(입력)
static int[][] ad = { { 0, 2, inf, inf, 5, inf, inf },
{ 2, 0, 3, 8, 1, inf, inf },
{ inf, 3, 0, 1, inf, inf, 4 },
{ inf, 8, 1, 0, 5, 1, 5 },
{ 5, 1, inf, 5, 0, inf, inf },
{ inf, inf, inf, 1, inf, 0, 1 },
{ inf, inf, 4, 5, inf, 1, 0 } };
static int[] dist = new int[nV]; // 최단거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단경로 저장 배열
public static void shortestPath(int start){
dist[start] = 0;
for( int j = 0; j < nV; j++)
{
int min = inf+1;
int index = -1;
// 시작정점에서 거리가 가장 작은 정점의 인덱스 파악
for(int k = 0; k < nV; k++){
if(visit[k] == false && min > dist[k]){
min = dist[k];
index = k;
}
}
visit[index] = true;
// 최단거리, 경로 업데이트
for(int l = 0; l < nV; l++)
if(ad[index][l] != 0 && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l];
path[l] = index; // 경로 업데이트
}
}
// 시작정점에서 각 정점까지 최단거리 출력
System.out.print("dist[] : ");
for (int i = 0; i < nV; i++)
System.out.print(dist[i] + " ");
System.out.println();
// 시작정점에서 각 정점까지 최단경로 출력에 활용되는 path[] 배열 출력
System.out.print("path[] : ");
for (int i = 0; i < nV; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args) {
for (int i = 0; i < nV; i++)
dist[i] = inf;
shortestPath(0);
}
}
path[] : 는 해당하는 인덱스의 정점에 방문하기 위해 거쳐오는 마지막 정점을 포함하는 배열
다익스트라 알고리즘에서는 dist[] 배열이 시작정점에서 각 정점까지의 최단거리 값을 저장한다. 시작정점에서 각 정점까지의 경로를 출력하기 위해서는 path[] 배열을 활용할 수 있다. path[] 배열에는 dist[] 배열의 값이 갱신될 때 마지막에 경유(방문)하는 정점을 저장한다. 다익스트라 알고리즘 종료 후 path[] 배열에 저장된 값을 스택을 활용하여 역추적하면 각 정점까지의 최단경로(시작정점에서부터 경유하는 모든 정점)를 출력할 수 있다. 다익스트라 알고리즘의 시간 복잡도는 정점의 개수가 일 때, 최단경로 계산 시 이중 루프를 활용하므로 이다.
추가 실습1) path 배열을 참조하여 최단 경로 출력
0 - 1 최단 경로 : 0 - 1
0 - 2 최단 경로 : 0 - 1 - 2
…
0 - 6 최단 경로 : 0 - 1 - 2 - 3 - 5 - 6
package s240604;
import java.util.*;
public class 추가실습1 {
static int nV = 7; // 정점 개수
static final int inf = 1000000; // 가중치 무한대 값 설정
// 인접 행렬로 표현된 가중치 그래프
static int[][] ad = {
{ 0, 2, inf, inf, 5, inf, inf }, // 정점 0의 간선들
{ 2, 0, 3, 8, 1, inf, inf }, // 정점 1의 간선들
{ inf, 3, 0, 1, inf, inf, 4 }, // 정점 2의 간선들
{ inf, 8, 1, 0, 5, 1, 5 }, // 정점 3의 간선들
{ 5, 1, inf, 5, 0, inf, inf }, // 정점 4의 간선들
{ inf, inf, inf, 1, inf, 0, 1 }, // 정점 5의 간선들
{ inf, inf, 4, 5, inf, 1, 0 } // 정점 6의 간선들
};
static int[] dist = new int[nV]; // 최단 거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단 경로 저장 배열
public static void shortestPath(int start) {
dist[start] = 0; // 시작 정점에서 자신까지의 거리는 0
for (int j = 0; j < nV; j++) { // 모든 정점에 대해 반복
int min = inf + 1;
int index = -1;
// 방문하지 않은 정점 중에서 가장 작은 거리를 가진 정점 찾기
for (int k = 0; k < nV; k++) {
if (!visit[k] && min > dist[k]) {
min = dist[k];
index = k;
}
}
if (index == -1) break; // 더 이상 접근할 수 없는 정점이 없으면 종료
visit[index] = true; // 해당 정점을 방문한 것으로 표시
// 인접한 정점들의 거리 갱신
for (int l = 0; l < nV; l++) {
if (ad[index][l] != inf && !visit[l] && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l]; // 거리 갱신
path[l] = index; // 경로 갱신
}
}
}
// 시작 정점에서 각 정점까지의 최단 경로 출력
for (int i = 0; i < nV; i++) {
System.out.print("0 - " + i + " 최단 경로 : ");
printPath(i);
System.out.println();
}
}
// 주어진 도착 정점까지의 경로를 출력하는 메서드
public static void printPath(int end) {
if (dist[end] == inf) { // 도착 정점이 접근 불가능한 경우
System.out.print("경로 없음"); // "경로 없음" 출력
return;
}
Stack<Integer> stack = new Stack<>(); // 경로를 저장할 스택
for (int at = end; at != -1; at = path[at]) { // 경로 배열을 역추적
stack.push(at); // 정점을 스택에 저장
}
// 스택에서 정점을 꺼내어 올바른 순서로 경로 출력
while (!stack.isEmpty()) {
System.out.print(stack.pop());
if (!stack.isEmpty()) System.out.print(" - ");
}
}
public static void main(String[] args) {
Arrays.fill(dist, inf); // 거리 배열을 무한대로 초기화
Arrays.fill(path, -1); // 경로 배열을 -1로 초기화 (경로 없음)
shortestPath(0); // 0번 정점에서 시작하는 최단 경로 계산
}
}
추가 실습2) 연습문제 5 해결
0 1 2 3 4 5 6
dist[] = 0 11 7 19 3 19 37
path[] = 0 0 4 4 0 2 5
0 - 6 최단 경로 : 0 - 4 - 2 - 5 - 6
package s240604;
import java.util.*;
/*
* 연습문제 5 해결
0 1 2 3 4 5 6
dist[] = 0 11 7 19 3 19 37
path[] = 0 0 4 4 0 2 5
* */
public class 추가실습2 {
static int nV = 7; // 정점 개수 : 7
static final int inf = 1000000; // 가중치 ∞ 값 설정
// 인접행렬로 표현된 가중치 그래프(입력)
static int[][] ad = { { 0, 11, 9, inf, 3, inf, inf },
{ 11, 0, inf, inf, 6, inf, 30 },
{ 9, inf, 0, inf, 19, 12, inf },
{ inf, inf, inf, 0, inf, inf, 21 },
{ inf, inf, 4, 16, 0, 21, 44 },
{ inf, inf, inf, inf, inf, 0, 18 },
{ inf, inf, inf, inf, inf, inf, inf } };
static int[] dist = new int[nV]; // 최단거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단경로 저장 배열
public static void shortestPath(int start){
dist[start] = 0;
for( int j = 0; j < nV; j++)
{
int min = inf+1;
int index = -1;
// 시작정점에서 거리가 가장 작은 정점의 인덱스 파악
for(int k = 0; k < nV; k++){
if(visit[k] == false && min > dist[k]){
min = dist[k];
index = k;
}
}
visit[index] = true;
// 최단거리, 경로 업데이트
for(int l = 0; l < nV; l++)
if(ad[index][l] != 0 && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l];
path[l] = index; // 경로 업데이트
}
}
// 시작정점에서 각 정점까지 최단거리 출력
System.out.print("dist[] : ");
for (int i = 0; i < nV; i++)
System.out.print(dist[i] + " ");
System.out.println();
// 시작정점에서 각 정점까지 최단경로 출력에 활용되는 path[] 배열 출력
System.out.print("path[] : ");
for (int i = 0; i < nV; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args) {
for (int i = 0; i < nV; i++)
dist[i] = inf;
shortestPath(0);
}
}
추가실습 3) 해당 문제 해결
0 1 2 3 4 5
dist[] = 0 @ @ @ @ @
dist[] = 0 7 9 @ @ 14
dist[] = 0 7 9 22 @ 14
dist[] = 0 7 9 20 @ 11
dist[] = 0 7 9 20 20 11
package s240604;
public class 추가실습3 {
static int nV = 6; // 정점 개수 : 7
static final int inf = 1000000; // 가중치 ∞ 값 설정
// 인접행렬로 표현된 가중치 그래프(입력)
static int[][] ad = { { 0, 7, 9, inf, inf, 14 }, // 0
{ 7, 0, 10, 15, inf, inf }, // 1
{ 9, 10, 0, 11, inf, 2 }, // 2
{ inf, 15, inf, 0, inf, 21}, // 3
{ inf, inf, inf, 6, 0, 9 }, // 4
{ 14, inf, 2, inf, 9, 0 }}; // 5
static int[] dist = new int[nV]; // 최단거리 저장 배열
static boolean[] visit = new boolean[nV]; // 방문 체크 배열
static int[] path = new int[nV]; // 최단경로 저장 배열
public static void shortestPath(int start){
dist[start] = 0;
for( int j = 0; j < nV; j++)
{
int min = inf+1;
int index = -1;
// 시작정점에서 거리가 가장 작은 정점의 인덱스 파악
for(int k = 0; k < nV; k++){
if(visit[k] == false && min > dist[k]){
min = dist[k];
index = k;
}
}
visit[index] = true;
// 최단거리, 경로 업데이트
for(int l = 0; l < nV; l++)
if(ad[index][l] != 0 && dist[l] > dist[index] + ad[index][l]) {
dist[l] = dist[index] + ad[index][l];
path[l] = index; // 경로 업데이트
}
}
// 시작정점에서 각 정점까지 최단거리 출력
System.out.print("dist[] : ");
for (int i = 0; i < nV; i++)
System.out.print(dist[i] + " ");
System.out.println();
// 시작정점에서 각 정점까지 최단경로 출력에 활용되는 path[] 배열 출력
System.out.print("path[] : ");
for (int i = 0; i < nV; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args) {
for (int i = 0; i < nV; i++)
dist[i] = inf;
shortestPath(0);
}
}