Declaratieve Talen/Oplossing Dijkstra Alternatief (Haskell)

Mogelijke oplossing

alleen het kortste pad wordt niet terug gegeven, hiervoor zou je bij uw afbeelding moeten bijhouden van welke knoop de waarde afkomstig is, zodat je deze op het einde achteruit kan doorlopen enzo het kortste pad kan contrueren.

import List

data Afstand = 	Waarde Int | Oneindig | Null
				deriving (Eq, Show)
type Pad = [String]

instance Ord Afstand where
	Oneindig <= Oneindig = True
	Oneindig <= Waarde a = False
	_ <= Oneindig = True
	Waarde a <= Waarde b = (a <= b)
	Null <= _ = False
	_ <= Null = False
	
	Oneindig >= _ = True
	Waarde a >= Oneindig = False
	Waarde a >= Waarde b = (a >= b)
	Null >= _ = False
	_ >= Null = False
	
	Oneindig < _ = False
	Waarde a < Oneindig = True
	Waarde a < Waarde b = (a < b)
	Null < _ = False
	_ < Null = False
	
	Oneindig > Oneindig = False
	Oneindig > _ = True
	Waarde a > Oneindig = False
	Waarde a > Waarde b = (a > b)
	Null > _ = False
	_ > Null = False

boog :: String -> String -> Afstand
boog x y 
	| boog2 x y == Null = boog2 y x
	| True = boog2 x y
	

boog2 :: String -> String -> Afstand
------------------------------------
boog2 "a" "b" = Waarde 10
boog2 "b" "e" = Waarde 8
boog2 "e" "f" = Oneindig
boog2 "f" "c" = Waarde 7
boog2 "c" "a" = Waarde 5
boog2 "c" "d" = Waarde 3
boog2 "d" "e" = Waarde 9
boog2 x y = Null

knopen :: [String]
------------------
knopen = ["a", "b", "c", "d", "e", "f"]

dijkstra :: String -> String -> (Afstand, Pad)
----------------------------------------------
dijkstra beginknoop eindknoop = 
	let
		-- zet T gelijk aan V
		t = knopen
		-- Definieer afbeelding L op V door L(a) = 0 L(x) = Oneindig
		afbeelding = [(beginknoop, Waarde 0)] ++ [ (x, Oneindig)  | x <- t, x /= beginknoop]
	in
		dijkstra2 beginknoop eindknoop t afbeelding
				 
dijkstra2 :: String -> String -> [String] -> [(String, Afstand)] -> (Afstand, Pad)
----------------------------------------------------------------------------------------------
dijkstra2 bk ek t a =
	let 
		-- Kies een v element van t met de kleinste L(v)
		kleinste@(ks, ka) = zoek_kleinste t a
		-- zet t gelijk aan t zonder v
		newt = delete ks t
		-- herberekn voor alle knopen y in t die verbonden zijn met knoop v, zet L(y) = min(L(y), L(v) + w(v,y))
		newa = herbereken ks ka a t
	in
		-- indien z geen element meer is van t dan stopt het algoritme
		if (not (elem ek newt))
		then (ka , knopen\\t)
		else dijkstra2 bk ek newt newa
			
herbereken :: String -> Afstand -> [(String, Afstand)] -> [String] -> [(String, Afstand)]
----------------------------------------------------------------------------
herbereken v lv [] t = []
herbereken v lv ((s,a):as) t =
	if ((elem s t) && ((boog v  s) /= Null))
	then 
		let 
			newa = min (plusafstand lv (boog v s)) a
		in
			(s, newa):herbereken v lv as t
	else (s,a):herbereken v lv as t
	
plusafstand :: Afstand -> Afstand -> Afstand
--------------------------------------------
plusafstand (Waarde a) (Waarde b) = 
	let
		newa = a+b
	in
		Waarde newa
plusafstand (Waarde a) Oneindig = Oneindig
plusafstand Oneindig (Waarde a) = Oneindig
plusafstand _ _ = Null
			
zoek_kleinste :: [String] -> [(String, Afstand)] -> (String, Afstand)
---------------------------------------------------------------------
zoek_kleinste t [(s, a)] = 
	if (elem s t)
	then (s,a)
	else ("geen knoop", Oneindig)
zoek_kleinste t ((s, a):xs) =
	let
		kleinste@(ks, ka) = zoek_kleinste t xs
	in
		if(a <= ka && (elem s t))
		then (s,a)
		else kleinste