Dijkstra's Algorithm
For rust, I’m updating the documentation for the standard library and specifically with the collections. For the priority queue I had the idea to use Dijkstra’s algorithm as a fun example. That idea was well received and that example is now live.
At first I wanted to use A* to solve the eight puzzle, which I’ve done before, but that example became far too big.
Here’s the example code currently up in docs:
Using rustc 0.12.0-pre (ef352faea84fa16616b773bd9aa5020d7c76bff0 2014-07-18 21:46:32 +0000
)
use PriorityQueue;
use uint;
// The priority queue depends on `Ord`.
// Explicitly implement the trait so the queue becomes a min-heap
// instead of a max-heap.
// `PartialOrd` needs to be implemented as well.
// Each node is represented as an `uint`, for a shorter implementation.
// Dijkstra's shortest path algorithm.
// Start at `start` and use `dist` to track the current shortest distance
// to each node. This implementation isn't memory efficient as it may leave duplicate
// nodes in the queue. It also uses `uint::MAX` as a sentinel value,
// for a simpler implementation.