- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
-- GUESS THE NAME OF "algorithmX":
import qualified Data.List as DL
infinity = 1/0
adjacencyMatrix =
[[0,3,1,6,0,0],
[3,0,5,0,3,0],
[1,5,0,5,6,4],
[6,0,5,0,0,2],
[0,3,6,0,0,6],
[0,0,4,2,6,0]] :: [[Double]]
replaceZerosWithInfinity matrix =
map (map (\e -> if e == 0 then infinity else e)) matrix
type Edge = (Int,Int,Double)
algorithmX adjacencyMatrix initialVertex = (minimumTotalCost,minimumEdges)
where
third (_,_,t) = t
minimumTotalCost = sum $ map third minimumEdges
(_,minimumEdges) = foldl iterate ([initialVertex],[]) [1..n-1]
matrix = replaceZerosWithInfinity adjacencyMatrix
n = length matrix
getIndexes visited =
filter (\(i,j) -> not $ elem j visited) [(i,j) | i <- visited, j <- [0..n-1]]
iterate :: ([Int],[Edge]) -> Int -> ([Int],[Edge])
iterate (visited,edges) iteration = (newVisited:visited,minimumEdge:edges)
where
(_,newVisited,_) = minimumEdge
minimumEdge = DL.minimumBy compareEdges $ map newEdge (getIndexes visited)
newEdge (i,j) = (i,j,matrix !! i !! j)
compareEdges e0 e1 = compare (third e0) (third e1)