Dijkstra's algorithm: Difference between revisions

Line 1,000:

===Dijkstra's algorithm===

//Dijkstra's algorithm

//Dijkstra's algorithm: Nigel Galloway, August 5th., 2018

[<CustomEquality;CustomComparison>]

type Dijkstra<'N,'G when 'G:comparison>={toN:'N;cost:Option<'G>;fromN:'N}

Line 1,014:

let inline Dijkstra N G y =

let rec fN l f=

if List.isEmpty l then ~~(y,~~f)

if List.isEmpty l then f

else let n=List.min l

if n.cost=None then ~~(y,~~f) else

if n.cost=None then f else

fN(l|>List.choose(fun n'->if n'.toN=n.toN then None else match n.cost,n'.cost,Map.tryFind (n.toN,n'.toN) G with

|Some g,None,Some wg ->Some {toN=n'.toN;cost=Some(g+wg);fromN=n.toN}

|Some g,Some g',Some wg when g+wg<g'->Some {toN=n'.toN;cost=Some(g+wg);fromN=n.toN}

|_ ->Some n'))((n.fromN,n.toN)::f)

fN (N|>List.map(fun n->{toN=n;cost=(Map.tryFind(y,n)G);fromN=y})) []

let r = fN (N|>List.map(fun n->{toN=n;cost=(Map.tryFind(y,n)G);fromN=y})) []

~~let~~ ~~dPath~~ (n~~,g) r=~~let rec fN z l=match List.tryFind(fun (_,g)->g=z) g with

(fun n->let rec fN z l=match List.tryFind(fun (_,g)->g=z) r with

|Some(n',g') when n=n'->Some(n'::g'::l)

|Some(n',g') when y=n'->Some(n'::g'::l)

|Some(n,g) ->fN n (g::l)

|Some(n',g') ->fN n' (g'::l)

|_ ->None

fN r []

fN n [])

</lang>

Line 1,033:

type Node= |A|B|C|D|E|F

let G=Map[((A,B),7);((A,C),9);((A,F),14);((B,C),10);((B,D),15);((C,D),11);((C,F),2);((D,E),6);((E,F),9)]

let n=Dijkstra [B;C;D;E;F] G A

let paths=Dijkstra [B;C;D;E;F] G A

printfn "%A" (~~dPath n~~ E)

printfn "%A" (paths E)

printfn "%A" (~~dPath n~~ F)

printfn "%A" (paths F)

</lang>