I have a problem: You want to go from point A to point B. Between every two nodes there is a normal road and then a carpool road. the carpool road is only available if you have a passenger with you. passengers can only be picked up from certain nodes. The carpool lane will always be faster or equal to the normal lane. This leads to situations where going our of your way to pick up a passenger and then back on the same route is worth it because it reduces overall cost.
I know that if I modify the edge costs so that these special nodes have negative costs I can then run bellman-ford but I am also required to come up with a solution that runs in O(ElogV) time. As far as I know djikstra’s is the fastest shortest path finding algorithm but because it is a greedy algorithm it will never traverse the same node twice. Hence, my problem. Now I realize I may be going about this the wrong way but I would appreciate any help.
Imagine two copies of your graph: G, and a new layer G'. G contains only "normal" roads, while G' contains all roads.
Now, wherever a road in G connects to a pickup node, connect that road to the corresponding node in G' instead.
In this new graph, use Dijkstra's algorithm to find the shortest path from A in G to either B or B' in G or G', and that will be your answer.
Note that you normally wouldn't really construct a new graph. Instead you would just implement Dijkstra's algorithm as if you had made the new graph.
This means that, instead of using just a vertex ID to represent a visited node, you would use a combination of a vertex ID and a Boolean that indicates whether you mean the one in G or the one in G', i.e., whether or not you've picked up a passenger.
This is operating on an implicit graph, which is actually the usual case when implementing simple graph algorithms.