Segment tree for graph problems

Revision en2, by ASHWANTH_K, 2024-11-01 08:04:24
  • 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)$$$), the goal is to perform Dijkstra algorithm on this dense graph and find out the shortest path 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: N = 6
U = 1
Lx = 3
Rx = 5
C = 2

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English ASHWANTH_K 2024-11-01 12:05:17 0 (published)
en9 English ASHWANTH_K 2024-11-01 12:04:45 805 Tiny change: 'ch of the M lines con' -> 'ch of the $M$ lines con'
en8 English ASHWANTH_K 2024-11-01 09:00:59 51 Tiny change: 'ke: \n[Imgur](https://' -> 'ke: \n[ ](https://'
en7 English ASHWANTH_K 2024-11-01 08:44:57 96 Tiny change: ' \n ![ ](https://' -> ' \n ![](https://'
en6 English ASHWANTH_K 2024-11-01 08:37:06 454
en5 English ASHWANTH_K 2024-11-01 08:31:48 486
en4 English ASHWANTH_K 2024-11-01 08:26:10 444
en3 English ASHWANTH_K 2024-11-01 08:16:41 967 Tiny change: ' \n \nExample: \n \n' -> ' \n \n**Example:** \n \n'
en2 English ASHWANTH_K 2024-11-01 08:04:24 508
en1 English ASHWANTH_K 2024-11-01 07:58:37 187 Initial revision (saved to drafts)