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) =
let mutable _ID = id
let mutable _neighbours:list = neighbours

member this.ID
with get() = _ID
and set(value) = _ID = [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 -> t
| h::t -> h::remove_first pred t
| _ -> [];

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

let rec Traverse (data:list, start:int, visited:list):list =
let startNode = List.find (fun (E:Node) -> E.ID = start) data //Get the starting node
let newData = remove_first (fun (E:Node) -> 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,_) -> contains i newVisited) startNode.Neighbours //Use only the neighbours that aren't visisted

if(List.isEmpty neighbourSet) then
newVisited;
else
neighbourSet
|> List.minBy (fun (_,d

Matthew Podwysocki wrote a nice functional solution for this on his blog a few years ago:

module Map =
  let transposeCombine m =
    (m, m) ||> Map.fold (fun acc k1 m' ->
      (acc, m') ||> Map.fold (fun acc' k2 v ->
        acc'
        |> Map.add k2 (Map.add k1 v (defaultArg (acc' |> 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)])
    ]
    |> Map.transposeCombine

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

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

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

Usage:

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

StackExchange Code Review Q#10663, answer score: 5