그래프이론, 최단경로 알고리즘 (벨만포드 플로이드 다익스트라 위상정렬 MST)

1. 다익스트라.

음수인 비용이 있으면 사용 불가능.

우선순위 큐를 사용해 출발점을 우선순위큐에 넣고 그리디하게 가장 거리가 짧은 타 정점으로 이동해서

해당 정점까지의 거리가 갱신된다면 우선순위큐에 추가.

방문한 정점은 다시 방문하지 않는다.

 

2. 벨만포드

V-1번 사이클을 돌면서 모든 정점에서 연결된 간선으로 근처 정점의 거리를 업데이트 한다.

V번째 사이클을 돌아 업데이트 되는 거리가 있다면 음수 사이클이 검출되는 것을 확인할 수 있다.

 

3. 플로이드

모든 정점간의 거리관계를 파악하는데에 가장 빠르다. 음수사이클은 검출불가.

간선을 입력받을 때, 이차원배열의 i에서 j까지의 거리를 모두 기록해둔다.

그후 3중 for문 돌면서. n번째 정점을 거치면  i에서 j까지의 거리가 더 짧아지는가를 확인하자.

i->j랑 i->n + n->j랑 뭐가 더 빠른지 확인해서 갱신하는 것.

 

4. 위상정렬

유향그래프, 싸이클없는케이스 만 가능하다.

a) dfs 돌려보면서 싸이클 있는지 판단한다. 검출되면 불가능판단. 그러면서 먼저 순회 끝난 노드를

스택에 넣고 출력한다.(스택이므로 역순으로출력될것)

b) 진입간선이 0인 노드를 큐에 넣는다. 큐에서 poll 하고 해당 노드에 연결된 간선을 모두 지운다.

업데이트된 진입간선 수로 반복한다.

 

5.

MST
그래프의 모든정점을 훑는 트리. 트리이므로 간선의 수는 정점-1이다.
정점-1개의 간선만 이용하고 최소한의 가중치로 연결해야 하므로
가중치 작은것부터 뽑아내는데, 이미 연결된 정점을 다른방식으로 연결하는건 빼고 한다.
연결됐는지는 유니온파인드로 하자. 유니온파인드는 항상 부모를 찾아서 union하기.