- Recently I came across a new idea to solve graph-related problems using segment trees, I would like to discuss the same with a problem.
Problem:
Given a graph $$$G$$$ with $$$N$$$ nodes and many edges (around $$$O(N^2)$$$), Goal is to perform the Dijkstra algorithm on this dense graph and find out the shortest path cost from node 1 to all other nodes.
The edges are given in a compressed format. The input follows $$$M$$$ lines. Each of the $$$M$$$ lines consists of 4 integers U Lx Rx C
meaning there are edges from node U
to all other nodes in range [Lx , Rx]
with cost C
. Edges are uni-directional.
Example:
For N = 6
, the edge-group U = 1 , [Lx,Rx] = [3,5] , C = 10
looks like:
Constraints:
- $$$1 \le N \le 10^5$$$
- $$$1 \le M \le 10^5$$$
- $$$1 \le U \le N$$$
- $$$1 \le Lx \le Rx \le N$$$
- $$$1 \le C \le 10^9$$$
Do spend some time thinking about this problem, before proceeding to the solution.
Initial Thought Process:
The main problem faced here is that in the worst case, we have plenty of edges $$$O(N^2)$$$, performing Dijkstra in this dense graph would lead to time complexity $$$O(N^2 log(N))$$$ which would give TLE. Also, it is not possible to store all edges in the adjacency list, giving MLE.
So we need to seek out some ways to reduce the number of edges so that time complexity can be improved.
- Our solution proceeds like this, first we try to convert this dense graph to a sparse graph with less number of edges and then perform the Dijkstra Algorithm to find our answer.
- Since the input of edges is also given in compressed format, intuitively we can think that there might be some ways to represent a group of edges as a single edge, so that we can reduce the number of edges and solve our problem.
Solution: Segment Tree as a structure
- One main observation in this problem is that we add edges from node
U
to a range of nodes[Lx, Rx]
. This gives an intuition that we deal with ranges and we can use segment trees to solve our problem. - In our solution, We only use the structure and ideas of segment tree (complete binary tree). We dont calculate or store anything in the segment tree nodes.
- First, we build a segment tree $$$G'$$$ with $$$N$$$ leaf nodes, ($$$2N$$$ nodes in total). These $$$N$$$ leaf nodes represent the $$$N$$$ nodes of the original graph $$$G$$$ and add edges from parent to its left and right children with 0 cost.
Example N = 8
- It is a well known fact that any range
[Lx , Rx]
can be covered by $$$O(log(N))$$$ nodes in a segment tree. So for every edge-groupU Lx Rx C
, we add edges from nodeU
to these $$$O(log(N))$$$ nodes with costC
.
Example: N = 8, U = 1, [Lx,Rx] = [3,8], C = 10
- Since from any intermediate node, we can visit the leaf nodes in its subtree with 0 cost, this graph $$$G'$$$ preserves the same information of graph $$$G$$$.
- Total number of edges is $$$2N$$$ (intial graph) + $$$M*logN$$$ (for each edge-group), So total edges are $$$E = O(Mlog(N))$$$.
- Performing dijkstra in this graph $$$G'$$$ would give time complexity $$$O(Mlog^2(N))$$$ which would pass under the given constraints.