combinatorial optimization: Dijkstra variants

Factual Questions
1

OK graph theorists … I’m in search of the following algorithms:

  1. one that describes shortest path between two nodes where a third node must be visited along the way or where a specific arc must be part of the solution. I guess this is a simplified TSP problem.

  2. a shortest path algorithm where the cost differs depending on the direction of travel, (not just one-way arcs)

  3. a version of Floyd’s algorithm that remembers the shortest path to each node and not just the distance.

  4. any other interesting Dijkstra variants

If you know of a good graph theory reference book, particularly one aimed at programmers, I’d love to hear about it.

2

1a) To find the shortest path between A and B, where point C must be visited along the way, find the shortest path between A and C, and then find the shortest path between C and B.

1b) To find the shortest path between A and B where arc CD must be part of the solution, find the shortest paths between A and C, and between D and B.

1c) To find the shortest path between A and B where either arc CD or arc DC must be part of the solution, calculate the distances AC, AD, CD, DC, CB, and DB. Compare the distances AC + CD + DB and AD + DC + CB.

  1. As long as you don’t have any negative distances, I can’t see how a direction-dependant distance changes any shortest-distance algorithm in the slightest.

  2. If Floyd’s algorithm is the breadth path search algorithm, have each node that you currently have a best guess at the shortest distance to it have a pointer to the node that immediately precedes it in that best path.

Sorry, no references, just memories from college.