# Finding the best path through the matrix in DTW

I have two time series q and c and I want to calculate dynamic time wrapping (DTW) distance between these two time series:

q<-c(1,3,4,5,6,7)
c<-c(2,3,1,5,3,4)


As I understand we should make a matrix like this:

4 | 9  1  0  1  4  9
3 | 16 0  1  4  9  16
5 | 16 4  1  0  1  4
1 | 0  4  9  16 25 36
3 | 4  0  1  4  9  16
------------------
1  3  4  5  6  7


I have read many references, but I could not understand how the finding the best path in this matrix works. Could you please explain to me how can to find the best path through this matrix, and then how can to calculate DTW?

• I'm not an expert in this area, but is your matrix missing a value in the bottom left corner? Not all rows/columns have the same number of elements. – Sycorax Jan 22 '14 at 16:01

You have presented a matrix showing the pointwise distance computed by using the squared Euclidean distance. Each element of this matrix will be referred to as cost[i,j].

You target is the accumulated distance matrix. Each element of this matrix will be referred to as DTW[i,j].

To compute the distance using this formula:

DTW[i, j] := cost[i,j] + minimum(DTW[i-1, j], DTW[i, j-1], DTW[i-1, j-1])

Two more requirements are to be defined:

• DTW[i, 0] = infinite
• DTW[0, j] = infinite

Then you can compute the first column and row such as:

4   33
3   24
5   20
1   4
3   4   4   5   9   18  34
1   3   4   5   6   7


Then, step by step, you iterate through the columns from left to right and you reach the target: the accumulated cost matrix.

4   33  9   8   9   13  22
3   24  8   9   13  18  26
5   20  8   9   9   10  14
1   4   8   13  21  34  54
3   4   4   5   9   18  34
1   3   4   5   6   7


The DTW distance is defined as the element DTW[n,m], thus the top right element of the accumulated distance matrix and it is the sum of the cost along the best possible warping path. Now you can use backtracking to identify the best possible warping path by iteratively choosing the minimum neighbour starting from the top right.

4           8   9   13  22
3       8
5       8
1   4
3   4
1   3   4   5   6   7


Finally it is important to mention that in most applications, the warping path is further constraints which can prevent pathological warping.