I am writing to see if someone can point me to the original citation (assuming that a single work can be pointed to) for the single-source shortest path problem in directed-acyclic graphs (DAGs). Below is one candidate citation, which I came up with after digging around on google scholar (somehow, though, 1977 already seems a bit late):

Donald Johnson. 1977. Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of ACM

As a more general point and question, I always find it quite hard as an outsider (I work in machine learning) to navigate the graph algorithms literature, given the interdisciplinary nature of the field. I imagine there might be some paper prior to the one cited above from pure maths or physics that uses non-standard notation (from today's standards), which makes it hard to verify that the algorithms are the same. Perhaps it makes sense to cite earlier review articles, such as the one above, that use modern notation (in which case, I can maybe just stick with citing Cormen). I'm curious what others think.

  • 4
    $\begingroup$ Problems that are as natural and old as this one sometimes don't have an "original citation". Plus, the original article (if one exists) is not always the best reference. A good general strategy is to follow references from articles you know; but that's a discussion for Academia. $\endgroup$ – Raphael Aug 22 '17 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.