ummels.de

Scala

Dijkstra in Scala

Dijkstra’s algorithm is a fundamental graph algorithm, which allows to compute the shortest path from a source node to a target node in a directed, weighted graph, i.e. the path with the smallest accumulated weight.

Priority Maps in Scala

In many algorithms—including Dijkstra’s algorithm for finding the shortest path between two vertices in a weighted graph—we need access to a data structure that maps elements to numbers or priorities where we can efficiently obtain and remove the element(s) with the least priority and add new elements as the algorithm progresses.