动态时间弯曲距离精确计算的Dijkstra方法

The Directed Graph Method for Dynamic Time Warping

将动态时间弯曲距离(DTW)的差异矩阵一一对应于点阵,按DTW定义的行走规则对该点阵连线定向,使所对应点阵成为一个有向图,然后使用一个加权技巧对该有向图的边加权后得到一个加权有向图,于是把求DTW的精确计算问题等价地转化为求一个有向图起点到终点的最短路长,从而使图论中求两点间最短路径的方法如目前公认的经典Dijkstra算法均可用于求DTW,因此间接地找到了精确计算DTW的一个新方法.

Map the difference matrix of dynamic time warping（DTW） to a corresponding point matrix,and connect those points according to the walking rout in the definition of DTW to obtain a directed graph.Then weight the edges by using some trick,a appropriate directed and weighted graph is given out.As a result,to find DTW is equally to find the shortest distance path,therefore all those algorithms that used to find shortest distance path such as Dijkstra＇s algorithm well known as the best one until now can be used to find DTW,which improves solving the problem of calculating DTW.