Dijkstra's (or other shortest path algorithm) where end node can be start node

Question

The traditional* implementation of Dijkstra's does not handle this case well. I think I've come up with some solutions that will work, but they are not particularly elegant**. Is this is a known problem with a standard solution?

This is assuming the non-trivial solution i.e. a path like A->B->C->A rather than just A->A.

* When I say traditional I mean marking each node as visited.

** Storing the number of times each node has been visited and basing the terminating conditions on whether the end node is the start node.

If the start and end nodes are the same, Dijkstra's works trivially well: it always finds a zero-length path, which of course is the shortest one possible. What are the other constraints you're not telling us about? — Sneftel
You could just add a special check for this special case at the beginning of the algorithm — But I'm Not A Wrapper Class
Can you elaborate about why a traditional implementation of Dijkstra's doesn't handle this case well? I've never had a problem with this case before. — templatetypedef
Sorry, yes I will elaborate. I mean assuming that you must find the non-trivial path. For example, A->B->C->A rather than A->A. I will update the question. — Clif Glass

Peter de Rivaz Peter de Rivaz · Accepted Answer · 2014-08-20T17:38:09

Split A into two nodes, called START and GOAL.

For any edge A->x add an edge START->x

For any edge y->A add an edge y->GOAL

Keep all other edges unchanged.

Then use normal Dijkstra to solve for the path from START to GOAL

Dijkstra's (or other shortest path algorithm) where end node can be start node

1 Answers