The "well known" path algorithms in this case are overkill; the graph is a tree. And Dijkstra is not really designed to handle negative edge weights (although i

The "well known" path algorithms in this case are overkill; the graph is a tree. And Dijkstra is not really designed to handle negative edge weights (although it would probably function correctly in this instance).