F# Djikstras shortest path implementation

Question

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<(int*int)>) =
 let mutable _ID = id
 let mutable _neighbours:list<(int * int)> = neighbours
 member this.ID
 with get() = _ID
 and set(value) = _ID <- value
 member this.AddNeighbour(id:int, distance:int) =
 let t:(int*int) = (id, distance)
 _neighbours <- _neighbours @ [t]
 member this.Neighbours
 with get() = _neighbours
 and set(value) = _neighbours <- value;
let nodes:list<Node> = [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<'a>) : bool =
 let filtered = List.filter (fun I -> I = item) lst;
 List.isEmpty(filtered);
let rec Traverse (data:list<Node>, start:int, visited:list<int>):list<int> =
 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:int) -> d) //Get neighbour with smallest distance
 |> fun (i, d) -> Traverse(newData, i, newVisited); //Recurse in to the traverse function, starting at the smallest neighbour
let result = Traverse (nodes, 1, []);
let writeList (lst:list<'a>):string =
 let mutable output = "";
 for I in lst do
 output <- String.Concat(output, I);
 output;
let path = "Output.txt";
File.WriteAllText(path , writeList(result));

Answer 1

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 < shortestKnownPath then
 accMap |> 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])