Inside
I should clarify at the outset that by “Dijkstra’s Algorithm” I mean “Dijkstra’s Algorithm for the shortest path problem (Dijkstra 1959) My main interest with regard to this famous algorithm is its relation to dynamic programming.
The usual Disclaimer
The objective of this page is not to teach you, dear reader, what “Dijkstra’s Algorithm” is all about. Rather, this page provide you with a rather broad description of the algorithm, and links to easily accessible material that you can use to study this subject on your own. This page is just a general preface to the conversations I have had with ChatGPT and Bart about this algorithm.
You don’t have to be an expert on this algorithm to understand and appreciate the issues I discuss with ChatGPT and Bart.
What is Dijkstra’s algorithm?
I had very interesting discussions with ChatGPT and Bard on this algorithm. Here are their perspectives on the algorithm. First, Bard’s
And here is ChatGPT’s:
The interesting thing about these essays is that they do not mention the fact that the algorithm is … a dynamic programming algorithm. This omission is the starting point for my conversations with ChatGPT and Bard on this algorithm.
The DP connection
Denardo (1982) showed that Dijkstra’s algorithm is a DP algorithm of a type that he called “reaching”. Sniedovich (2006, 2010) argued that the term “push” is more appropriate.
For some unexplained reason, this very important fact is not mentioned, let alone discussed, in popular computer science textbooks on Algorithms (e.g., Cormen et al. 2009).
In the Dynamic Programming page I discuss in more details between dijkstra’s Algorithm and other types of dynamic programming algorithms.
The Module
All you have to do to experiment with our exciting Dijkstra’s Algorithm module is click the image. The online module will appear in a new window.
ChatGPT’s and Bard’s
Bibliography
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2009). Introduction to Algorithms. Third Edition, MIT Press.
- Dijkstra (1959) A Note on Two Problems in Connexion with Graph. Numerische Mathematik 1:269-271.
- Denardo, E.V. (1982) Dynamic Programming — models and applications.Prentice-Hall.
- Sniedovich, M. (2006) Dijkstra’s algorithm revisited: The dynamic programming connexion. Control and Cybernetics 35(3): 599-620. download
- Sniedovich, M. (2010) Dynamic Programming — foundations and principles. CRC Press.