Dijkstra's Algorithm is used to find the best path between the nodes of a directed graph. This could be used to find directions between places on a map, routing network traffic or to direct AI controlled entities in video games.
There are faster ways to calculate paths (such as the A* algorithm) but they are variations on this Algorithm, so if you can understand this then you should not have too much trouble adapting it to better Algorithms.
This code is a very crude example of Dijkstra's path finding Algorithm in C++ (Visual Studio 2010 / CodeBlocks GCC Projects)
cGraph- The graph containing all nodescNode- A node in the GraphcEdge- An edge that joins one node to another with a "cost" value
The program creates a simple graph in main.cpp and calculate a few paths between some of the nodes in the graph.
It will then print out the path to get to that node backwards.
`
-= Example using Dijkstra's Algorithm to calculate paths between connected nodes =
----------------
Calculated path from A to D
D <- A
----------------
----------------
Calculated path from D to A
A <- C <- D
----------------
----------------
Calculated path from A to E
NOT REACHABLE
----------------
----------------
Calculated path from A to A
A
----------------
`
This is implemented quite crudely but serves as a simple and easy to follow example of how to implement this Algorithm in code.
Tested it compiling and running as a console app on Win32 in Visual Studio 2010 or CodeBlocks IDE using GCC compiler on Linux Ubuntu.
- It doesn't maintain a "Fringe" list of nodes to check, it just checks all unvisted nodes every time
- It's not thread safe as it's storing path values in the cNode class
- The resulting path is simply printed out backwards, you could implement a stack to push it onto it if you wanted
- Isn't robust - doesn't do any checking for null parameters to functions
- Dijkstra Algorithm Example - https://www.youtube.com/watch?v=0nVYi3o161A
- Wikipedia Entry - http://en.wikipedia.org/wiki/Dijkstra's_algorithm