F# Djikstras shortest path implementation I'm just getting my feet wet with F#, by implementing some simple algorithms. First up: Djikstras shortest path.

There is one piece I've written in this code which confuses me as to why it works: the contains function. As I understand it, List.isEmpty returns true when a list is empty; but in this case, I would want to see the opposite of that. However, not(List.isEmpty) appeared to give the opposite of what I was expecting: it still returned true on a list being empty. Why is this the case? Or am I just missing something obvious?

As for the full code listing: have I done anything massively wrong?

open System;
open System.Collections;
open System.Collections.Generic;
open System.IO;


type Node(id: int, neighbours:list&lt;(int*int)&gt;) =
    let mutable _ID = id
    let mutable _neighbours:list&lt;(int * int)&gt; = neighbours

    member this.ID
        with get() = _ID
        and set(value) = _ID &lt;- value

    member this.AddNeighbour(id:int, distance:int) =
        let t:(int*int) = (id, distance)
        _neighbours &lt;- _neighbours @ [t]

    member this.Neighbours
        with get() = _neighbours
        and set(value) = _neighbours &lt;- value;

let nodes:list&lt;Node&gt; = [new Node(1, [(2, 3); (3, 3); (4, 1)]);
                        new Node(2, [(3, 1)]);
                        new Node(3, [(1, 3); (2, 1); (4, 10)]);
                        new Node(4, [(1, 1); (3, 10)])
                        ];

let rec remove_first pred lst =
        match lst with
        | h::t when pred h -&gt; t
        | h::t -&gt; h::remove_first pred t
        | _ -&gt; [];

let contains (item:'a) (lst:list&lt;'a&gt;) : bool =
    let filtered = List.filter (fun I -&gt; I = item) lst;
    List.isEmpty(filtered);

let rec Traverse (data:list&lt;Node&gt;, start:int, visited:list&lt;int&gt;):list&lt;int&gt; =
    let startNode = List.find (fun (E:Node) -&gt; E.ID = start) data //Get the starting node
    let newData = remove_first (fun (E:Node) -&gt; E.ID = startNode.ID) data //Get the new data by removing the start node from the current data
    let newVisited = visited@[startNode.ID]
    let neighbourSet = List.filter (fun (i,_) -&gt; contains i newVisited) startNode.Neighbours //Use only the neighbours that aren't visisted

    if(List.isEmpty neighbourSet) then
        newVisited;
    else
        neighbourSet
        |&gt; List.minBy (fun (_,d:int) -&gt; d) //Get neighbour with smallest distance
        |&gt; fun (i, d) -&gt; Traverse(newData, i, newVisited); //Recurse in to the traverse function, starting at the smallest neighbour

let result = Traverse (nodes, 1, []);

let writeList (lst:list&lt;'a&gt;):string =
    let mutable output = "";
    for I in lst do
        output &lt;- String.Concat(output, I);
    output;

let path = "Output.txt";
File.WriteAllText(path , writeList(result));
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])