Segment tree for graph problems

Правка en10, от ASHWANTH_K, 2024-11-01 12:05:17
  • 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-group U Lx Rx C, we add edges from node U to these $$$O(log(N))$$$ nodes with cost C.

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.

Problems using this idea:

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский ASHWANTH_K 2024-11-01 12:05:17 0 (published)
en9 Английский ASHWANTH_K 2024-11-01 12:04:45 805 Tiny change: 'ch of the M lines con' -> 'ch of the $M$ lines con'
en8 Английский ASHWANTH_K 2024-11-01 09:00:59 51 Tiny change: 'ke: \n[Imgur](https://' -> 'ke: \n[ ](https://'
en7 Английский ASHWANTH_K 2024-11-01 08:44:57 96 Tiny change: ' \n ![ ](https://' -> ' \n ![](https://'
en6 Английский ASHWANTH_K 2024-11-01 08:37:06 454
en5 Английский ASHWANTH_K 2024-11-01 08:31:48 486
en4 Английский ASHWANTH_K 2024-11-01 08:26:10 444
en3 Английский ASHWANTH_K 2024-11-01 08:16:41 967 Tiny change: ' \n \nExample: \n \n' -> ' \n \n**Example:** \n \n'
en2 Английский ASHWANTH_K 2024-11-01 08:04:24 508
en1 Английский ASHWANTH_K 2024-11-01 07:58:37 187 Initial revision (saved to drafts)