- 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
.
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$$$
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 lead to TLE. Also, it is not possible to store all edges in an adjacency list, which would lead to MLE.
- So we have to seek out some ways to reduce the number of edges so that time complexity can be improved.
- Our solution proceeds like this, we first 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 given in compressed format, 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. - 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 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 its leaf nodes in 0 cost, this graph $$$G'$$$ preserves the same information of graph $$$G$$$.
- Total number of edges is $$$2N$$$ (intial graph) + $$$MlogN$$$, 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.