Review 10 - Single-Source-Shortest Path in C++

https://eglife.tistory.com/103

Review 9 - MST(Minimum Spanning Trees) in C++

Graph의 path와 관련된 알고리즘이다.

 

특정 노드에서 출발하는 가장 짧은 path를 찾는 알고리즘!

 

대표적으로 Dijkstra, Bellman Ford 알고리즘이 있고 추가로 Directed acyclic 그래프에 대해서도 shortsest path를 찾아봅시다.

 

Graph는 방향성이 있는 grapg로 가정하자.

 

Shortest path란 그 path를 구성하는 모든 edge들의 weight을 합쳤을 때 그 값이 가장 작은 녀석을 말하는 것이다.

 

 

1. Shortest paths problems

그 중에 "Single Source"란 graph G = ( V, E )가 주어졌을 때, 특정 vertex s에서 출발하여 모든 vertex를 훑는 root를 찾는다.

 

이와 대비되는 개념이 All-Pairs Shortest path인데, 이건 모든 vertex가 source이며 동시에 target이 된다.

shortest path 안에 있는 path들은  다 특정 node 사이의 shortest path들이다.

 

그리고 negative cycle을 포함하고 있는 graph는 shortest path를 갖지 않는다.

 

shortest path는 negative cycle은 당연히 없고( - 로 발산), positive cycle도 갖지 않는다.

 

이유는, 그 cycle을 뺀 다른 shortest path를 정의할 수 있기때문이다.

 

Shortest Path Tree와 Minimum spanning tree의 차이점은,

 

MST는 딱 1개 존재하지만, SPT 는 많다.

 

MST는 모든 Vertex를 포함하는 연결 중 weight이 Minimum인 것을 뜻하고,

SPT는 특정 Source => Target Vertex를 이어주는 path 중 min 값을 찾는 건데, 이 path가 여러 개 있을 수 있다.

 

 

2. SSSP Algorithm

 

모든 vertex v는 2개의 value를 저장한다. 

dist(s) = 0 , pred(s) = NULL 로 일단 알고리즘을 시작한다.

 

그리고 중요한 것이 Relaxation! 지금 이 path가 정말 shortest path가 맞는지 판단하는 부분이다.

vertex u, v 사이의 weigh과 u의 dist가 v의 dist보다 작을 때만 업데이트를 한다.

 

정리를 하자면,

Dijkstra , Bellman - Ford , Directed acyclis graph의 특징은 추후에 다룬다.

 

3. Unweighted graph에서 Shortest path 찾기

사실 별거 없다. 그냥 Queue를 이용해서 BFS를 실행하면 된다.

 

코드를 한 번 직접 짜보는 것을 추천한다. Queue + BFS / Stack + DFS

 

 

4. Dijkstra's Algorithm

 

- 기본적으로 Weighted  / Directed graph이며 nonnegative weight EDGE를 가정하고, 사실 Graph에 대한 BFS 일반화 느낌이다.

 

- Greedy Strategy를 사용한다. 현재 시점에서 가장 가깝고, Weigth이 작은 vertex를 찾아서 방문set인 set S에 저장한다. 이 때, 가장 작은 순서대로 vertex를 하나하나 더해가야 하기 때문에 Data Structure로 Priority Queue를 많이 쓰며, 이 Prioirty Queue는 보통 Heap 구조로 표현되어 있다.

 

Dijkstra algorithm의 pseudo 코드는 아래와 같다.

저 위에 Relax 부분이 가장 중요한 파트다.

 

Priority Queue에 들어 있는 Node의 distance는 전부 0으로 되어 있을텐데, 특정 Node( = Vertex)가 방문되어서 Shortest path에 포함이 되었따면, 그 Node의 distance는 더 이상 0이 아니고 그 놈과 이어지는 u(Vertex)의 distance에다가 u&v 사이에 weight값을 더한 것으로 Update를 시켜줘야 한다.

 

이 때, Prioirity queue의 구조인 Heap의 성질을 유지하기 위해서 heapify를 해줘서 적절한 위치에 Update된 Node가 자리할 수 있게 해야 한다.

 

 

Dijkstra 알고리즘의 Time Complexity는 O(VlogV + ElogV)이다. 보통 Edge의 수가 더 많고 영향력이 크기 때문에 그냥 O(ElogV)로 알고 있어도 지장이 없다.

 

이는, Minmum Spanning Tree를 구할 때 썼던, Prims / Kruskal과 비슷한 수치이다.

 

 

5. Bellman - Ford 알고리즘

 

Dijkstra 알고리즘의 치명적인 단점은 Edge에 Negative weight이 있으면 안 된다는 것이다.

이처럼 한 번 방문 set으로 옮겨진 edge를 다시 꺼내어 수정할 수 없기 때문이다.(위 그림에서 vertex b)

 

그래서 나온 개념이 벨망포드 알고리즘!

 

가장 작은 vertex를 고르는 것이 아니라, 전체 edge 중에서 작은 놈부터 udate해가는 개념이다. 이 edge가 vertex랑 연결되어 있는지 아닌지는 볼 필요가 없다.

 

그래서 다익스트라 보다는 속도가 느리지만 대신 Negative edge를 컨트롤 할 수 있는 것이다. Trade Off !

모~~든 Edge들을 방문하고 체크한다. 기본적으로 negative cycle이 있으면 False를 반환하게 setting을 하고, 일반 cycle이 있으면 solution은 없다.

 

Iteration은 Vertces 개수 -1 만큼만 하면 된다. 생각해보면 Vertex 5개라고 할 때, 이 놈들 다 잇는 Shortest path는 4개만 있으면 된다. 즉 V-1개!

 

Negative cycle 감지는, V-1회 돌고, cycle 한 번 더 돌렸을 때 distnace update가 발생하면 Detect 한 것이다!

- Routing 순서 선택에 많이 쓰인다고 한다. 선택이 필요한 라우터를 Negative weight으로 설정해서 pick이 빨리 되게 하는 방법!

 

 

6. Shortest Paths for Directed Acyclic Graph ( D A G )

 

말 그대로 싸이클이 없는 그래프이고, Negative edge는 있지만 negative cycle은 없는 녀석이다.

 

이 경우, 위상정렬 -> topological sort를 vertex에 먼저 해주고, Relax를 시작한다.

Topological sort를 할 때는 Stack or Recursive를 이용한 DFS를 사용해주고, 통상 O(V+E)시간이 걸린다.

 

 

이렇게 쓰이는 경우가 많다..

 

C++ Shortest path, All path, DP, Red - black tree.. 할 게 너무나도 많아버린다...!

 

 

- E. O. D -