F# Djikstras shortest path implementation
Matthew Podwysocki wrote a nice functional solution for this on his blog a few years ago:



module Map =
  let transposeCombine m =
    (m, m) ||&gt; Map.fold (fun acc k1 m' -&gt;
      (acc, m') ||&gt; Map.fold (fun acc' k2 v -&gt;
        acc'
        |&gt; Map.add k2 (Map.add k1 v (defaultArg (acc' |&gt; Map.tryFind k2) Map.empty))
    ))

type City =
    | Boise   | LosAngeles | NewYork | Seattle
    | StLouis | Phoenix    | Boston  | Chicago
    | Denver

let distanceBetweenCities =
  Map.ofList
    [
        (Boise, Map.ofList [(Seattle, 496);(Denver, 830);(Chicago, 1702)]);
        (Seattle, Map.ofList [(LosAngeles, 1141);(Denver, 1321)]);
        (LosAngeles, Map.ofList [(Denver, 1022);(Phoenix, 371)]);
        (Phoenix, Map.ofList [(Denver, 809);(StLouis, 1504)]);
        (Denver, Map.ofList [(StLouis, 588);(Chicago, 1009)]);
        (Chicago, Map.ofList [(NewYork, 811);(Boston, 986)]);
        (StLouis, Map.ofList [(Chicago, 300)]);
        (Boston, Map.ofList [(StLouis, 986)]);
        (NewYork, Map.ofList [(Boston, 211)])
    ]
    |&gt; Map.transposeCombine

let shortestPathBetween startCity endCity =
  let rec searchForShortestPath currentCity distanceSoFar citiesVisitedSoFar accMap =
    let visitDestinations m =
      (m, distanceBetweenCities.[currentCity])
        ||&gt; Map.fold
          (fun acc city distance -&gt;
             searchForShortestPath city (distance + distanceSoFar) (citiesVisitedSoFar @ [city]) acc)

    match Map.tryFind currentCity accMap with
    | None -&gt; accMap |&gt; Map.add currentCity (distanceSoFar, citiesVisitedSoFar) |&gt; visitDestinations
    | Some x -&gt;
        let (shortestKnownPath, _) = x
        if distanceSoFar &lt; shortestKnownPath then
          accMap |&gt; Map.add currentCity (distanceSoFar, citiesVisitedSoFar) |&gt; visitDestinations
        else accMap

  let shortestPaths = searchForShortestPath startCity 0 [] Map.empty
  shortestPaths.[endCity]


Usage:

shortestPathBetween LosAngeles NewYork //(2721, [Denver; StLouis; Chicago; NewYork])