WonYong-Jang
commented
5 years ago SPFA ( Shortest Path Faster Algorithm)
- 벨만포드 알고리즘의 성능을 향상시킨 알고리즘
- 시간 복잡도 O(V*E)이지만 실제로는 훨씬 빨리 돌아가는 알고리즘으로 O(V+E) 혹은 O(E)
- 음수 간선에도 사용가능하기 때문에 MCMF에서 자주 사용
- 벨만포드와 SPFA는 같은 아이디어지만 차이점은
==> 벨만포드는 모든 간선에 대해 업데이트를 진행
==> SPFA는 바뀐 장점과 연결된 간선에 대해서만 업데이트를 진행
배열 dist => queue를 이용하여 최단 거리를 구함
inQ 는 큐에 해당 정점이 큐에 들어있는지 확인하는 배열 / 이미 큐에 들어가 있지 않은 정점들만 넣어줌
음수 사이클 확인 : 한 정점이 n 번이상 방문되면 그 정점을 포함하여 음수 사이클이 있다는 것을 할수 있음
타임머신 소스코드
public class Main {
static int N, M;
static int INF = 987654321;
static ArrayList<ArrayList<Node>> adj = new ArrayList<>();
static int[] dis = new int[505];
static int[] inQ = new int[505];
static int[] cycle = new int[505];
static Queue<Integer> que = new LinkedList<>();
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i=0; i<= N; i++) {
adj.add(new ArrayList<>());
dis[i] = INF;
}
int dx =0, dy =0, cost = 0;
for(int i=1; i<= M; i++) {
st = new StringTokenizer(br.readLine());
dx = Integer.parseInt(st.nextToken());
dy = Integer.parseInt(st.nextToken());
cost = Integer.parseInt(st.nextToken());
adj.get(dx).add(new Node(dy, cost));
}
que.add(1);
dis[1] = 0; //최단 거리 배열
inQ[1] = 1; // 큐에 들어있는지 확인 배열
cycle[1]++;
while(!que.isEmpty())
{
int cur = que.poll();
inQ[cur] = 0;
for(Node next : adj.get(cur))
{
if(dis[next.dx] > next.cost + dis[cur])
{
dis[next.dx] = next.cost + dis[cur];
if(inQ[next.dx] == 0)
{
cycle[next.dx]++;
if(cycle[next.dx] >= N) {
System.out.println(-1);
return;
}
inQ[next.dx] = 1;
que.add(next.dx);
}
}
}
}
for(int i=2; i<= N; i++)
{
if(dis[i] == INF) System.out.println(-1);
else System.out.println(dis[i]);
}
}
static class Node {
int dx, cost;
Node(int a, int b) {
dx=a; cost=b;
}
}
}
다익스트라 알고리즘은
그래프의 어떤 정점 하나를 시작점으로 선택하고, 나머지 정점들로의 최단거리를 모두 구함 시작점 자신은 0 정점 개수가 V, 간선 개수가 E일 때 기본적인 최적화를 거치면 O(ElogV)의 시간복잡도
// 인접 리스트 정점 갯수만큼 할당 해주고 인접리스트 연결 할 것 // dis 배열 모두 INF 로 초기화 해주고 시작점 0으로 놓고 시작 ! public static void solve() { PriorityQueue que = new PriorityQueue<>(new Mysort());
que.add(new Node(S,0)); // 시작점
dis[S] = 0;
}
/**
*/ public class Main {
static int N, M; static int[][] data = new int[6001][3]; // input 간선 표 static int[] d = new int[501]; // cost 정보 배열 static final int INF = 6005*10000; public static void main(String[] args) throws IOException { int dx,dy,cost; for(int i=1; i<= M; i++) { data[i][0] = dx; data[i][1] = dy; data[i][2] = cost; }
} }