# Does the "prize-collecting shortest path problem" exist?

The prize collecting shortest path problem (PCSPP) is a special case of the prize collecting Steiner tree problem (PCSTP) (PCSPP is the PCSTP with only two terminal vertices, namely the source and sink nodes of the PCSPP). I am aware of quite some work on the PCSTP (by Ivana Ljubic amongst others) but I have never seen specialized algorithms for the PCSPP. Do such algorithms exist?

You can make the graph directed, push the prizes into the arcs and solve a shortest path problem with negative lengths (i.e. for an undirected graph $$G=(V,E)$$ with distances $$d_e\geq 0$$, $$e\in E$$ and prizes $$p_v\geq 0$$, $$v\in V$$, construct a directed graph $$G'=(V,A)$$, where $$A$$ is obtained by replacing each edge $$e=\{u,v\}\in E$$ of length $$d_e$$ by two arcs $$(u,v)$$ of length $$d_e-p_v$$ and $$(v,u)$$ of length $$d_e-p_u$$.)