[궁극의 웰노운 알고리즘] 2. dial's algorithm, O(1) LCA, Pie for a Pie trick, incremental SCC
이전에는 다항식을 예고했었지만, 다항식에 대해 글을 작성하기에는 아직 정보가 부족하다고 판단되어 그냥 적당히 작성해볼만하고, 알아두면 좋을 것 같지만 그렇게 많이 알려져있다고 생각되지는 않는 그래프 이론의 아이디어들을 들고 왔다. 1. dial's algorithm 일반적인 무향 그래프의 한 점에서 다른 점들로의 최단경로를 검색하는 것은 다익스트라 알고리즘을 통해 수행할 수 있다는 사실이 잘 알려져있다. 그러나, 다익같은 경우에는 로그가 하나 붙기 때문에, 비정상적으로 정점이나 간선이 많은 경우에 대해서는 적용하기 힘들다. 하지만 만약 특수하게 각 간선들에 대한 가중치가 작다면, dial's algorithm을 사용하면 O(NK+M)만에 이를 수행할 수 있다는 것이 알려져있다. 이때, N은 정점개수, M..
