Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a number of different 'misspelled' words w1, w2, ... , wn and a dictionary D compute the editing distances between all words wi and all words di in the dictionary and, for every wi, output the word(s) in the dictionary with the smallest editing distance from wi.

At the moment this is how I've implemented my algorithm;

main():
minDistance = 1000 // arbitrary large number
Let D be the dictionary
Let W be the set of words that needs ‘correcting’
For every w in W:
For every d in D:
dist = distance(w, d)
if dist < minDistance:
minDistance = dist
Make a linked list minList and add d to it
if dist == minDistance:
Add d to minList
Output minDistance aswell as minList

distance(w, d):
Make a matrix M with dimensions (m,n)
If the last d and this d has any p (start)-letters in common => use M(m, p) from last computation (no need to compute it again)
Fill the first row and the first column with their respective ‘index’ //Look at table on Wiki
For col = 1 to m:
For row = p to n:
wagner-fischer(w, d, col, row)

wagner-fischer(w, d, col, row):
res = M(col-1, row-1) + (1 if w have the same letter at index col-1 as d at row-1)
addLetter = M(col-1, row) + 1
deleteLetter = M(col, row-1) + 1
if addLetter < res: