- 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