dijkstra - v0.1.1

dijkstra

Types

AllShortestPaths

</>

Same as ShortestPaths, except for dijkstra_all. The distances field is the same as ShortestPaths since there is only one shortest distance. But the predecessors field has a list of predecessors for each node instead of a single predecessor, to represent the possibility of there being multiple paths that result in the same shortest distance.

pub type AllShortestPaths(node_id) {
  AllShortestPaths(
    distances: Dict(node_id, Int),
    predecessors: Dict(node_id, List(node_id)),
  )
}

Constructors 

  • AllShortestPaths(
  distances: Dict(node_id, Int),
  predecessors: Dict(node_id, List(node_id)),
)

ShortestPaths

</>

The return type of dijkstra. Consists of two dictionaries that contain, for every visited node, the shortest distance to that node and the node’s immediate predecssor on that shortest path.

pub type ShortestPaths(node_id) {
  ShortestPaths(
    distances: Dict(node_id, Int),
    predecessors: Dict(node_id, node_id),
  )
}

Constructors 

  • ShortestPaths(
  distances: Dict(node_id, Int),
  predecessors: Dict(node_id, node_id),
)

SuccessorsFunc

</>

A function that given a node, returns successor nodes and their distances.

pub type SuccessorsFunc(node_id) =
  fn(node_id) -> Dict(node_id, Int)

Functions

dijkstra

</> 
pub fn dijkstra(
  edges_from: fn(a) -> Dict(a, Int),
  start: a,
) -> ShortestPaths(a)

Run Dijkstra’s algorithm to determine the shortest path to every node reachable from start, according to edges_from.

Examples

let f = fn(node_id: NodeId) -> Dict(NodeId, Int) {
  case node_id {
    0 -> dict.from_list([#(1,4), #(2,3)])
    1 -> dict.from_list([#(3,5)])
    2 -> dict.from_list([#(3,5)])
    3 -> dict.from_list([])
    _ -> panic as "unreachable"
  }
}

dijkstra.dijkstra(f, 0)
// -> ShortestPaths(dict.from_list([#(0, 0), #(1, 4), #(2, 3), #(3, 8)]), dict.from_list([#(1, 0), #(2, 0), #(3, 2)]))

dijkstra_all

</> 
pub fn dijkstra_all(
  edges_from: fn(a) -> Dict(a, Int),
  start: a,
) -> AllShortestPaths(a)

Same as dijkstra, except each node predecessor is a list instead of a single node. If there are multiple shortest paths, junction nodes will have more than one predecessor.

has_path_to

</> 
pub fn has_path_to(paths: ShortestPaths(a), dest: a) -> Bool

Return true if Dijkstra’s algorithm found a path to the dest node.

Recall that in order to determine the shortest path, Dijkstra’s algorithm visits all nodes reachable from the given start node. Thus we can exploit that to determine whether any particular node is reachable, without looking at the graph again.

shortest_path

</> 
pub fn shortest_path(
  paths: ShortestPaths(a),
  dest: a,
) -> #(List(a), Int)

When applied to the result of dijkstra, returns the shortest path to the dest node as a list of successive nodes, and the total length of that path.

shortest_paths

</> 
pub fn shortest_paths(
  all_paths: AllShortestPaths(a),
  dest: a,
) -> #(List(List(a)), Int)

Same as shortest_path, except for dijkstra_all.

✨ Search Document