# combinatorial optimization: Dijkstra variants

**URL:** <https://boards.straightdope.com/t/combinatorial-optimization-dijkstra-variants/116434>\
**Category:** Factual Questions\
**Created:** [June 28, 2002, 6:34pm UTC](https://boards.straightdope.com/t/combinatorial-optimization-dijkstra-variants/116434 "2002-06-28T18:34:35Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![evilhanz](https://avatars.discourse-cdn.com/v4/letter/e/ba8739/32.png) [@evilhanz](https://boards.straightdope.com/u/evilhanz)\
**Post date:** [June 28, 2002, 6:34pm UTC](https://boards.straightdope.com/t/combinatorial-optimization-dijkstra-variants/116434/1 "2002-06-28T18:34:35Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [June 28, 2002, 8:14pm UTC](https://boards.straightdope.com/t/combinatorial-optimization-dijkstra-variants/116434/2 "2002-06-28T20:14:02Z")

</div>

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.