You need another nested loop to get it to work the way that you've indicated. Here's the corrected pseudocode.
let n be the number of vertices
initialize cost <- 0
initialize checkThese <- [0]
initialize checked <- [true, false, ..., false] (length n)
repeat n - 1 times (alternatively, test for termination as indicated)
smallest <- infinity
argSmallest <- null
for v in checkThese
for w from 0 to n - 1
let cost = matrix[min(v, w)][max(v, w)]
if not checked[w] and cost < smallest then
smallest <- cost
argSmallest <- w
end if
end for
end for
(break here if argSmallest is null)
cost <- cost + smallest
add argSmallest to checkThese
checked[argSmallest] <- true
end repeat
This is not an especially efficient realization of Prim's algorithm. To speed it up from O(n^3) to O(n^2), the asymptotic optimum for dense matrices, you can maintain another n-element array of integers, call it minCost
. The entry at index w
is the minimum cost of an edge from a checked vertex to w
. The revised pseudocode looks like this.
let n be the number of vertices
initialize cost <- 0
initialize checked <- [true, false, ..., false] (length n)
initialize minCost <- [0, infinity, ..., infinity] (length n)
repeat n - 1 times (alternatively, test for termination as indicated)
smallest <- infinity
argSmallest <- null
for w from 0 to n - 1
if not checked[w] and minCost[w] < smallest then
smallest <- minCost[w]
argSmallest <- w
end if
end for
(break here if argSmallest is null)
cost <- cost + smallest
checked[argSmallest] <- true
minCost[argSmallest] <- 0
for v from 0 to n - 1
let cost = matrix[min(argSmallest, v)][max(argSmallest, v)]
if not checked[v] and cost < minCost[v] then
minCost[v] <- cost
end if
end for
end repeat
If all of the edge costs are positive, then you can replace the test checked[w]
with minCost[w] > 0
and do away with the checked
array. You also could fuse the two loops.