Safe Haskell	None
Language	Haskell2010

Dijkstra

Description

Dijkstra's algorithm

An algorithm to find multi-source shortest paths in a graph with non-negative edges.

There are a variety of possible implementations depending on what is required, such as finding parents, early stopping, etc. This is a basic implementation calculating only the distances, to be modified when required.

Sources:

Edgar W. Dijkstra, "A note on two problems in connexion with graphs", 1959 https://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf
Implementation is folklore

Synopsis

dijkstra :: LGraph Weight -> [Vertex] -> UArray Vertex Weight
dijkstraH :: LGraph Weight -> [Vertex] -> UArray Vertex Weight
type Weight = Int

Documentation

dijkstra :: LGraph Weight -> [Vertex] -> UArray Vertex Weight Source #

Runs Dijkstra's algorithm on the given graph. Unreachable vertices have distance maxBound. O((V + E) log V).

dijkstraH :: LGraph Weight -> [Vertex] -> UArray Vertex Weight Source #

Runs Dijkstra's algorithm on the given graph. srcs should not have duplicates. Unreachable vertices have distance maxBound. Faster than dijkstra, especially for large sparse graphs. O((V + E) log E).

type Weight = Int Source #