벨만포드 알고리즘을 처음 사용해봤다.

벨만포드는 다익스트라보다 느리고, 비슷하다.

다익스트라랑 다른 점은 음수가중치가 존재해도 사용이 가능하다는 것이다.

그런데 다익스트라보다 시간복잡도가 O(VE)로 크다. 다익스트라는 O(ElgV)

import java.io.*;
import java.util.*;
/**
* BOJ 11657 타임머신
* https://gist.github.com/KSH-code/db82f6fce9c81d50ce203417a159206a
*/
class Bus{
public int s, e ,w;
public Bus(int s, int e, int w) {
this.s = s;
this.e = e;
this.w = w;
}
}
public class Main{
private static final int MAX = 124124124;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1[] = br.readLine().split(" ");
int N = Integer.parseInt(str1[0]);
int M = Integer.parseInt(str1[1]);
Bus bus[] = new Bus[M];
int dist[] = new int[N+1];
Arrays.fill(dist, MAX);
dist[1] = 0;
for(int i = 0; i<M; i++){
String str2[] = br.readLine().split(" ");
int u = Integer.parseInt(str2[0]);
int v = Integer.parseInt(str2[1]);
int w = Integer.parseInt(str2[2]);
bus[i] = new Bus(u, v, w);
}
if(BellmanFord(dist, bus, N, M)){
for (int i = 2; i <=N; i++){
System.out.println(dist[i] == MAX ? -1 : dist[i]);
}
}else{
System.out.println(-1);
}
}
private static boolean BellmanFord(int dist[], Bus bus[], int N, int M){
for(int i = 1; i<=N; i++){
for(int j = 0; j<M; j++){
if(dist[bus[j].e] > bus[j].w + dist[bus[j].s]){
dist[bus[j].e] = bus[j].w + dist[bus[j].s];
}
}
}
for (int i = 0; i<M; i++)
if(dist[bus[i].e] > bus[i].w + dist[bus[i].s])
return false;
return true;
}
}
view raw Main.java hosted with ❤ by GitHub



저작자표시

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

2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번)  (0) 2017.10.20
BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선)  (0) 2017.10.19
BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18

다익스트라에 이어서 플로이드 워셜 알고리즘을 공부했다.


다익스트라를 모든 정점에서 돌리면 플로이드 워셜이 된다.

그런데 다익스트라는 음수 가중치를 가지는 간선이 있으면 안된다 한다.


플로이드 워셜은 모든 정점을 돌아보기 때문에 시간복잡도가 O(V^3)이다.



입력에서 중복값 확인을 해주니 정답이 됐다.


위키백과에 JAVA코드도 추가했다.



import java.io.*;
import java.util.*;
/**
* BOJ 11404 플로이드
*/
public class Main{
private static final int MOD = (int)(1e+9)+7;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int V = Integer.parseInt(br.readLine());
int E = Integer.parseInt(br.readLine());
int d[][] = new int[V + 1][V + 1];
for(int i = 1; i<=V; i++){
Arrays.fill(d[i], Integer.MAX_VALUE);
d[i][i] = 0;
}
for (int i = 0; i<E; i++){
String str1[] = br.readLine().split(" ");
int a = Integer.parseInt(str1[0]);
int b = Integer.parseInt(str1[1]);
int c = Integer.parseInt(str1[2]);
d[a][b] = Math.min(c, d[a][b]);
}
floyd(d, V);
for(int i = 1; i<=V; i++){
for(int j = 1; j<=V; j++){
bw.write(d[i][j] + " ");
}
bw.write("\n");
}
bw.flush();
}
private static void floyd(int d[][], int V){
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++) {
if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) continue;
if (d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
view raw Floyd-Warshall.java hosted with ❤ by GitHub

위키백과 JAVA

저작자표시

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

BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18
BOJ 1717 집합의 표현 disjoint-set  (0) 2017.10.17
BOJ 1753 최단경로 다익스트라 알고리즘 (Dijkstra)  (0) 2017.10.17

나무위키에 올라온 사진들을 보며 코드를 작성했다.



MAX값을 2147483647 즉 signed int 의 MAX로 하다보니, 출력에서 꼬여가지고 출력초과과 떴었다.

백준의 출력 용량은 최대 1 MB이다


그 다음에 MAX값을 변경해서 제출하니 시간초과가 뜨는 것이다.

우선순위 큐로 작업하지않고, 리스트에 다 담아서 작업했었음.


그래서 큐에서 값이 변경될 경우에 offer해줬고, 성공했다.




import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
public int V,W;
public Node(int V, int W){
this.V = V; // U -> V 할때 V
this.W = W; // U -> V 의 가중치
}
@Override
public int compareTo(Node arg0) {
return this.W - arg0.W; // 오름차순 정렬
}
}
/**
* BOJ 1753 최단경로
*/
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// Node 개수와 엣지 개수를 입력받음
String str1[] = br.readLine().split(" ");
int V = Integer.parseInt(str1[0]);
int E = Integer.parseInt(str1[1]);
PriorityQueue<Node> edges[] = new PriorityQueue[V+1];
Queue<Integer> tempQueue = new LinkedList<>();
for(int i = 1; i<=V; i++)
edges[i] = new PriorityQueue<>();
// 시작 정점 입력받고, 가중치 배열 생성
int K = Integer.parseInt(br.readLine());
int W[] = new int[V+1];
Arrays.fill(W, 9898798);
W[K] = 0;
// 시작정점 담아준다.
for(int i = 0; i<E; i++){
String str2[] = br.readLine().split(" ");
int u = Integer.parseInt(str2[0]);
int v = Integer.parseInt(str2[1]);
int w = Integer.parseInt(str2[2]);
edges[u].offer(new Node(v, w));
}
tempQueue.offer(K);
while(!tempQueue.isEmpty()){
int s = tempQueue.poll(); // 시작
Iterator it = edges[s].iterator();
while(it.hasNext()){
Node tempNode = (Node) it.next();
if (W[tempNode.V] > tempNode.W + W[s]) {
tempQueue.add(tempNode.V);
}
W[tempNode.V] = Math.min(tempNode.W + W[s], W[tempNode.V]);
}
}
// 값 출력
for(int i = 1; i<=V; i++){
if(W[i] == 9898798)
bw.write("INF");
else
bw.write(String.valueOf(W[i]));
bw.write("\n");
}
bw.flush();
}
}
view raw Dijkstra.java hosted with ❤ by GitHub
저작자표시

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

BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18
BOJ 11404 플로이드 Floyd-Warshall  (0) 2017.10.18
BOJ 1717 집합의 표현 disjoint-set  (0) 2017.10.17

+ Recent posts

티스토리툴바