# GNMGraph::KShortestPaths redundantly re-sums root path cost on every spur iteration

[KinshukSS2]

What is the bug?

In GNMGraph::KShortestPaths (gnm/gnmgraph.cpp) the is redundant calculations..
whenever it sees a new path variation it calculates from the beginning itself
because the starting section of the path doesn't change during these steps,
the algo can be more efficient by remembering that initial cost and then only calculating the new branches

Steps to reproduce the issue

1. build GDAL with GNM support enabled.
2. create a GNM file network with a long chain of weighted nodes/edges
3. call GetPath(start_fid, end_fid, GATKShortestPath, ["num_paths=20"]).
4. profile or instrument KShortestPaths -the inner cost-summation loop
   iterates the entire merged path on every spur attempt, re-summing the same
   root edges repeatedly.

Versions and provenance

• OS: Linux Ubuntu 24.04
• GDAL version: 3.13.0 master

Additional context

this fix is just perfomance based gives the same correctness as the existing one ..
it passes all the 8 existing GNM autotests as well

the old approach scaled quadraticallyin root path length.
the fix reduces it to linear

this fix also resolve the TODO comments that were already present

[KinshukSS2]

hope the current method was not done due to some constraint that needed to be in check or maybe because it only plays a role in long paths