shortestpath

BFS: E

Dijikstra: ElogV or V^2

E가 완전그래프처럼 많으면 V^2이 유리하고 E가 V와 비슷할정도로 적으면 ElogV가 VlogV정도가 되서 더 유리하다.

Floyd: V^3

Bellman-ford: VE

참고로 벨만포드에서 완화는 항상 완화된 정점에 인접한 정점에서만 일어나므로 다음에 완화할 정점을 Q로 관리하기만 하면 약간 최적화된다. 이게 SPFA라고하는 휴리스틱이고, 몇가지 휴리스틱과 결합해서 사용했을때 평균O(E)정도 복잡도를 기대할수 있다고 하는데 격자형태 그래프에서 저격됬던거로 기억한다.

Possible Pitfalls

음수사이클 관련해서는 Tricky한 케이스들이 몇 있다.

1. 다익스트라에서는 음수간선 존재할시 결과값이 이상해지는게 아니라 복잡도가 2^N 이상이 되서 터진다.
2. s에서 e로가는 경로만 볼 때, 그에 영향을 주지 않는(=같은 컴포넌트에 속하지 않는) 음수사이클이 검출되는 경우를 처리해줘야하는 경우가 있다. 이를 처리해주려면 destination부터 시작하는 역간선 bfs로 도달가능한 간선만 사용하면 된다.
3. 음의 셀프루프