'알고리즘' 카테고리의 글 목록

# 다익스트라 알고리즘은 어떠한 정점을 기준으로 잡고 다른 모든 정점으로의 최단 거리를 구하는 알고리즘이고, 플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘이다. 다익스트라는 가장 적은 비용을 가지는 간선을 하나씩 선택하여 알고리즘을 수행했다면, 플로이드 와샬은 거쳐가는 정점을 기준으로 알고리즘을 수행했다는 점이 특징이다.

다익스트라는 그리디 기법을 기반 / 플로이드 와샬은 다이나믹 프로그래밍 기반

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

반복문 3개를 중첩하기 때문에, 시간 복잡도는 O(V^3)로 복잡하다.



public class floydwarshall {
	static int INF = 999999;
	public static void main(String[] args) {
		
		int arr[][] = {{0,   1,   INF, 4, 5},
                       {INF, 0,   3,   2, 1},
                       {1,   INF, 0,   5, 3},
                       {INF, INF, 4, 0, 2},
                       {4, INF, 1, 7, 0}};
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				for(int k=0; k<arr.length; k++) {
					if(arr[j][k] > arr[j][i] + arr[i][k])
						arr[j][k] = arr[j][i] + arr[i][k];
				}
			}
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				System.out.print(arr[i][j]+ " ");
			}System.out.println();
		}
		
	}
}

'알고리즘' 카테고리의 다른 글

#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java (0)	2020.01.11
#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java (0)	2020.01.09
#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08

벨만 포드 알고리즘은, 다익스트라에서 할 수 없었던 음의 가중치도 계산 할 수 있도록 한 방식이다. 하지만 모든 정점에서 모든 간선을 다 봐야하기 때문에 시간 복잡도가 더 높다. 필요에 맞게 잘 사용하는 것이 중요.

벨만 포드 알고리즘에 대한 전제 조건

최단 경로는 사이클을 포함할 수 없다. 따라서 최대 |V|-1개의 간선만 사용할 수 있다.
최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해준다. 이때 만약 음의 값을 가지고 있는 간선으로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.)

이를 위해 백준에 있는 https://www.acmicpc.net/problem/11657 문제를 풀어 보는 것이 좋다. 꼭 풀어 보는 것을 추천한다.

처음 반복문을 돌려 최소 거리를 구하여 dist 배열을 갱신한다. 그 후에는 음의 값을 가지고 있는 간선으로 인해 싸이클이 형성되는 케이스를 체크해주어 해결하면 된다.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class bellmanford {
	static int INF = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Edge e[] = new Edge[M];
		
		int dist[] = new int[N+1];
		for(int i=1; i<=N; i++)
			dist[i] = INF;
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			e[i] = new Edge(u,v,val);
		}
		
		dist[1] = 0;
		
		for(int i=0; i<N-1; i++) {
			for(int j=0; j<M; j++) {
				if(dist[e[j].u] == INF) 
					continue;
				if(dist[e[j].v] > (dist[e[j].u] + e[j].val)) {
					dist[e[j].v] = dist[e[j].u] + e[j].val;
				}
			}
		}
		
		boolean check = false;
		
		for(int i=0; i<M; i++) {
			if(dist[e[i].u] == INF)
				continue;
			if(dist[e[i].v] > dist[e[i].u] + e[i].val) {
				check = true;
				break;
			}
		}
		
		if(check)
			System.out.println(-1);
		else {
			for(int i=2; i<=N; i++) {
				if(dist[i] == INF)
					System.out.println("-1");
				else
					System.out.println(dist[i]);
			}
		}
		
	}
	
	public static class Edge{
		int u;
		int v;
		int val;
		public Edge(int u,int v, int val) {
			this.u = u;
			this.v = v;
			this.val = val;
		}
	}
}

'알고리즘' 카테고리의 다른 글

#알고리즘_플로이드 와샬(Floyd-Warshall Algorithm) - Java (0)	2020.01.11
#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java (0)	2020.01.09
#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08

1. 조합(Combination)

서로 다른 n개에서 r개를 뽑는 경우 => (n)C(r) => n! / (n-r)! * r!

2. 중복 조합(Combination with repetition)

서로 다른 n개에서 r개를 뽑는 데, r개의 요소가 중복되어도 상관 없음 nHr => (n+r-1)C(r) (n-r+1)! / ( (n-r)! * r!))

3. 순열(Permutation)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열 => nPr => n!/(n-r)!

4. 중복 순열(Permutation with repetition)

서로 다른 n개의 원소에서 r개를 중복으로 골라 순서에 상관있게 나열 => n^r

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

import java.util.ArrayList;

public class combination {

static int arr[] = { 1, 3, 5, 7, 9 };

static boolean visit[] = new boolean[arr.length];

static int cnt=0;

static ArrayList<Integer> arrList = new ArrayList<>();

public static void main(String[] args) {

combination(arrList, arr.length, 3, 0);

System.out.println("Count = "+cnt);

System.out.println();

cnt=0;

arrList = new ArrayList<>();

combination_repetition(arrList, arr.length, 3, 0);

System.out.println("Count = "+cnt);

System.out.println();

cnt=0;

arrList = new ArrayList<>();

permutation(arrList, visit, arr.length, 3);

System.out.println("Count = "+cnt);

System.out.println();

cnt=0;

arrList = new ArrayList<>();

permutation_repetition(arrList, arr.length, 3);

System.out.println("Count = "+cnt);

}

// 조합 = 서로 다른 n개에서 r개를 뽑는 경우 => (n)C(r) => n! / (n-r)! * r!

public static void combination(ArrayList<Integer> arrList, int n, int r, int index) {

if(r==0) {

for(int i=0; i<arrList.size(); i++) {

System.out.print(arrList.get(i)+" ");

}System.out.println();

cnt++;

return;

}

if(index == n)

return;

arrList.add(arr[index]);

combination(arrList, n, r-1, index+1); //뽑았음-> r-1

arrList.remove(arrList.size()-1); //위에서 뽑은거 롤백

combination(arrList, n, r, index+1); //안뽑았으니 r

}

// 중복 조합 = 서로 다른 n개에서 r개를 뽑는 데, r개의 요소가 중복되어도 상관 없음 nHr => (n-r+1)C(r) (n-r+1)! / ( (n-r)! * r!))

public static void combination_repetition(ArrayList<Integer> arrList, int n, int r, int index) {

if(r==0) {

for(int i=0; i<arrList.size(); i++) {

System.out.print(arrList.get(i)+" ");

}System.out.println();

cnt++;

return;

}

if(index == n)

return;

arrList.add(arr[index]);

combination_repetition(arrList, n, r-1, index); //뽑았음-> r-1 중복을 허용하니까 index는 고정

arrList.remove(arrList.size()-1); //위에서 뽑은거 롤백

combination_repetition(arrList, n, r, index+1); //안뽑았으니 r, index+1

}

// 순열 = 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열 => nPr => n!/(n-r)!

public static void permutation(ArrayList<Integer> arrList, boolean[] visit, int n, int r) {

if(arrList.size() == r) {

for(int i : arrList) {

System.out.print(i+" ");

}System.out.println();

cnt++;

return;

}else {

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

if(!visit[i]) {

visit[i] = true;

arrList.add(arr[i]);

permutation(arrList, visit, n, r);

arrList.remove(arrList.size()-1);

visit[i] = false;

}

// 중복 순열 = 서로 다른 n개의 원소에서 r개를 중복으로 골라 순서에 상관있게 나열 => n^r

public static void permutation_repetition(ArrayList<Integer> arrList, int n, int r) {

if(arrList.size() == r) {

for(int i : arrList) {

System.out.print(i+" ");

}System.out.println();

cnt++;

return;

}else {

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

arrList.add(arr[i]);

permutation_repetition(arrList, n, r);

arrList.remove(arrList.size()-1);

}

Colored by Color Scripter

cs

'알고리즘' 카테고리의 다른 글

#알고리즘_플로이드 와샬(Floyd-Warshall Algorithm) - Java (0)	2020.01.11
#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java (0)	2020.01.11
#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08

탐색 문제를 해결하는 방법 2가지

선형 탐색(순차 검색) : 순서대로 하나씩 비교하면서 찾기
이진 탐색 : 반씩 범위를 줄여 나가면서 찾기

선형 탐색은 순서대로 하나씩 비교하면서 찾는 방법으로 시간 복잡도는 O(N)이다.

이진 탐색은 크기를 비교하며 반씩 줄여나가므로 배열이 정렬되어있다는 가정하에 진행한다. 따라서 배열이 정렬 되어있지 않다면 이진 탐색을 사용할 수 없다. 이진 탐색의 시간 복잡도는 O(log N)이다.

이진 탐색의 장점은 선형 탐색보다 탐색 속도가 빠르지만, 정렬되어 있어야 한다는 단점이 있다.

이진 탐색의 메카니즘

정렬된 배열의 중간에 임의의 값을 찾고자하는 값과 비교하여

1) 만약 중간의 값이 더 작다면 중간의 값을 제외한 배열의 우측 데이터들을 대상으로 탐색을 진행한다.

2) 만약 중간의 값이 더 크다면 중간의 값을 제외한 배열의 좌측 데이터들을 대상으로 탐색을 진행한다.

3) 1,2) 를 반복하며 만약 중간의 값과 찾고자 하는 값이 동일하다면 알고리즘을 중단한다.

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

41

import java.util.Arrays;

public class search {

public static void main(String[] args) {

int arr[] = { 12,4,7,2,9,15,29,41};

System.out.println(linear_search(arr, 2));

Arrays.sort(arr);

System.out.println(binary_search(arr, 2));

}

public static int linear_search(int arr[], int val) {

for(int i=0; i<arr.length; i++) {

if(arr[i] == val) {

return i;

}

return -1;

}

public static int binary_search(int arr[], int val) {

int begin = 0;

int end = arr.length-1;

int middle;

while(begin<=end) {

middle = (begin+end)/2;

if(val == arr[middle])

return middle;

else if(val > arr[middle]) {

begin = middle + 1;

}else {

end = middle-1;

}

return -1;

}

Colored by Color Scripter

cs

'알고리즘' 카테고리의 다른 글

#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java (0)	2020.01.11
#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java (0)	2020.01.09
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java (0)	2020.01.07

신장 트리 (Spanning Tree)

1. 그래프의 모든 정점이 간선으로 연결되어 있다.

2. 그래프 안에 사이클이 포함되어 있지 않다.

최소 신장 트리(Minimum Spanning Tree)

말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리

Prim, Kruskal 알고리즘은 최소 신장 트리를 구하는 방법이다. 두 알고리즘 모두 Greedy Method를 기반으로 한다.

'알고리즘' 카테고리의 다른 글

#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java (0)	2020.01.09
#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java (0)	2020.01.07
#알고리즘_다익스트라(Dijkstra Algorithm) - Java (0)	2020.01.07

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 알고리즘이다.

쉽게 말하면 프림 알고리즘은 지금까지 연결된 정점에서 연결된 간선들 중 사이클을 만들지 않고 최소의 값을 갖는 간선을 하나씩 선택하면서 MST를 만들어가는 방식이다.

프림 알고리즘은 시작 정점을 정하고, 시작 정점에서 가까운 정점을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않는다. 그에 반해 크루스칼 알고리즘은 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하면서 MST를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야 한다. 이 때, Union-Find(Disjoint-Set) 방법을 이용하여 사이클을 확인한다.

시간 복잡도

프림 : O(V^2+E) → O(E logV)
크루스칼 : O(E logE)

**프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘

**시간 복잡도는 비슷하지만, 보통 밀집한 그래프의 경우 프림이, 그렇지 않은 경우에는 크루스칼이 유리하다.

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Queue;

import java.util.Scanner;

public class prim {

static int V,E;

static boolean visit[];

static ArrayList<Edge>[] graph;

static ArrayList<Edge> MST;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

V = sc.nextInt();

E = sc.nextInt();

graph = new ArrayList[V+1];

visit = new boolean[V+1];

for(int i=0; i<=V; i++)

graph[i] = new ArrayList<>();

MST = new ArrayList<>();

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

int u = sc.nextInt();

int v = sc.nextInt();

int val = sc.nextInt();

graph[u].add(new Edge(u, v, val));

graph[v].add(new Edge(v, u, val));

}

int point = 1;

solve(point);

for(int i=0; i<MST.size(); i++) {

System.out.println(MST.get(i).begin + " " +MST.get(i).end+" "+MST.get(i).value);

}

private static void solve(int P) {

// TODO Auto-generated method stub

PriorityQueue<Edge> pq = new PriorityQueue<>();

Queue<Integer> queue = new LinkedList<>();

queue.add(P);

while(!queue.isEmpty()) {

int now = queue.poll();

visit[now] = true;

for(Edge e : graph[now]) {

if(!visit[e.end])

pq.add(e);

}

while(!pq.isEmpty()) {

Edge e = pq.poll();

if(!visit[e.end]) {

queue.add(e.end);

visit[e.end] = true;

MST.add(e);

break;

}

public static class Edge implements Comparable<Edge>{

int begin;

int end;

int value;

public Edge(int b, int e, int v) {

this.begin = b;

this.end = e;

this.value = v;

}

@Override

public int compareTo(Edge o) {

// TODO Auto-generated method stub

return this.value - o.value;

}

Colored by Color Scripter

cs

'알고리즘' 카테고리의 다른 글

#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java (0)	2020.01.07
#알고리즘_다익스트라(Dijkstra Algorithm) - Java (0)	2020.01.07
#알고리즘_정렬(Insertion, Bubble, Selection, Quick, Heap, Merge) - Java (0)	2020.01.06

탐욕적인 방법(greedy)를 이용하여 네트워크의 모든 정점을 최소비용으로 연결하는 최적해답을 구하는 알고리즘이다.

**싸이클을 허용하지 않기 때문에 싸이클을 체크하기 위해 Union-find 사용

알고리즘 매커니즘 => 간선을 하나씩 선택해서 MST를 찾는 알고리즘

최초, 모든 간선을 가중치(Edge value)에 따라 오름차순으로 정렬한다.
가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.
만약 사이클이 존재하면 다음으로 가중치 낮은 간선을 선택한다. (사이클 확인은 union-find를 이용)
N-1개의 간선이 MST에 더해질때 까지 2,3를 반복한다.

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

package graph;

import java.util.ArrayList;

import java.util.PriorityQueue;

import java.util.Scanner;

public class k {

static int V, E;

static PriorityQueue<Edge> pq;

static ArrayList<Edge> MST;

static int parent[];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

V = sc.nextInt();

E = sc.nextInt();

pq = new PriorityQueue<>();

MST = new ArrayList<>();

parent = new int[V+1];

// for init

for(int i=0; i<=V; i++)

parent[i] = i;

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

int u = sc.nextInt();

int v = sc.nextInt();

int val = sc.nextInt();

pq.add(new Edge(u, v, val));

}

while(MST.size() < (V-1)) {

Edge e = pq.poll();

if(find(e.begin) != find(e.end)) {

MST.add(e);

union(e.begin, e.end);

}

for(int i=0; i<MST.size(); i++) {

System.out.println(MST.get(i).begin+" "+MST.get(i).end+" "+MST.get(i).val);

}

public static int find(int n) {

if(n==parent[n])

return n;

else {

int p = find(parent[n]);

parent[n] = p;

return p;

}

public static void union(int n1, int n2) {

int p1 = find(n1);

int p2 = find(n2);

if(p1!=p2) {

parent[p1] = p2;

}

public static class Edge implements Comparable<Edge>{

int begin, end, val;

public Edge(int b, int e, int v) {

this.begin=b;

this.end=e;

this.val=v;

}

@Override

public int compareTo(Edge o) {

// TODO Auto-generated method stub

return this.val - o.val;

}

Colored by Color Scripter

cs

'알고리즘' 카테고리의 다른 글

#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08
#알고리즘_다익스트라(Dijkstra Algorithm) - Java (0)	2020.01.07
#알고리즘_정렬(Insertion, Bubble, Selection, Quick, Heap, Merge) - Java (0)	2020.01.06

다익스트라 알고리즘은 하나의 정점에서 다른 정점까지 최단경로를 구하는 알고리즘이다.

** 최단 경로(Shortest Path)문제는 정점 u, v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 것

**다익스트라는 가중치가 양수여야 한다. 음수인 경우에는 벨만포드 알고리즘으로 해결

** 다익스트라는 그리디 기법을 기반으로 하기 때문에 추후에 가중치가 감소를 야기하는 음수를 가진 가중치가 있어서는 안된다. ( 근시적인 관점을 유지하기 때문에 추후에 가중치가 감소하는 것을 고려하지 못함)

** 다익스트라는 그리디 기법 기반, 벨만 포드는 dynamic Programming 이라 생각하면 된다. 즉 모든 경우를 확인할 수 있기에 위와 같은 문제가 발생하지 않는다

이 알고리즘의 기본 로직은 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며 최단거리를 갱신하는 것이다.

알고리즘 매커니즘

방문(visit)되어 있지 않은 정점 중에서 Dist의 값이 가장 작은 min 값과 index를 찾는다.
index를 True로 체크한다.
index와 연결된 모든 정점을 검사한다.
간선을 index, X, Y 라고 했을 때 dist[Y] > d[index] + ad[index][Y]이면 갱신
위 과정을 모든 정점을 수행할때까지 반복한다.

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

import java.util.Scanner;

public class dijkstra {

static int ad[][];

static int dist[];

static boolean visit[];

static int E,V;

static int INF=9999999;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

V = sc.nextInt();

E = sc.nextInt();

ad = new int[V+1][V+1];

dist = new int[V+1];

visit = new boolean[V+1];

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

int u = sc.nextInt();

int v = sc.nextInt();

int val = sc.nextInt();

ad[u][v] = ad[v][u] = val;

}

for(int i=1; i<=V; i++) {

dist[i] = INF;

}

solve(1, 8);

}

private static void solve(int begin, int end) {

// TODO Auto-generated method stub

dist[begin] = 0;

String str = "";

//find min

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

int min = 9999;

int index = -1;

for(int j=1; j<=V; j++) {

if(visit[j] == false && min > dist[j]) {

min = dist[j];

index = j;

}

visit[index] = true;

str += index + " ";

for(int k=1; k<=V; k++) {

if(ad[index][k] != 0 && dist[k] > dist[index] + ad[index][k])

dist[k] = dist[index] + ad[index][k];

}

for(int i=1; i<=V; i++)

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

System.out.println('\n'+str);

}

Colored by Color Scripter

cs

'알고리즘' 카테고리의 다른 글

#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08
#알고리즘_크루스칼(Kruskal Algorithm) - Java (0)	2020.01.07
#알고리즘_정렬(Insertion, Bubble, Selection, Quick, Heap, Merge) - Java (0)	2020.01.06

uk's study

알고리즘

#알고리즘_플로이드 와샬(Floyd-Warshall Algorithm) - Java

'알고리즘' 카테고리의 다른 글

#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java

'알고리즘' 카테고리의 다른 글

#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java

1. 조합(Combination)

2. 중복 조합(Combination with repetition)

3. 순열(Permutation)

4. 중복 순열(Permutation with repetition)

'알고리즘' 카테고리의 다른 글

#알고리즘_선형 탐색/이진 탐색 - Java

이진 탐색의 메카니즘

'알고리즘' 카테고리의 다른 글

#알고리즘_신장 트리(Spanning Tree)

신장 트리 (Spanning Tree)

최소 신장 트리(Minimum Spanning Tree)

'알고리즘' 카테고리의 다른 글

#알고리즘_프림(Prim Algorithm) - Java

시간 복잡도

'알고리즘' 카테고리의 다른 글

#알고리즘_크루스칼(Kruskal Algorithm) - Java

'알고리즘' 카테고리의 다른 글

#알고리즘_다익스트라(Dijkstra Algorithm) - Java

'알고리즘' 카테고리의 다른 글

+ Recent posts

티스토리툴바