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}{\lambda }_1+a_{e,2}{\lambda }_2+a_{e,3}{\lambda }_3+\cdots +a_{e,d}{\lambda }_d+a_{e,d+1}.$$ Here…