Shortest Paths with Linear Edge Weights

Suryajith Chillara, Kshitij Gajjar, Nithish Raja

We study shortest paths in directed graphs whose edge weights are of the form $$\mathsf{wt}(e)=a_{e,1}\hat{I}{»}_1+a_{e,2}\hat{I}{»}_2+a_{e,3}\hat{I}{»}_3+\cdots +a_{e,d}\hat{I}{»}_d+a_{e,d+1}.$$…