最短路径问题是图论和算法设计中的经典问题,也是现实世界的许多应用中的基本问题。然而,在现实世界中的路网图都具有动态性,不同的时刻对应不同的数据,这种图中两节点间最短路径的定义及其算法都不同于传统最短路径问题。而且传统的路径寻优只考虑了源点和终点,不能满足实际应用中的一些需求。对以上问题进行研究具有广泛的理论研究价值和实际应用价值。本文针对动态最短路径问题进行了较为深入的研究。具体工作如下:(1)改进了Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径,即有向图的节点之间除了静态的距离外,还有动态的速度和代价,例如城市交通中的高峰与非高峰时段影响速度/时间,收费与非收费路段影响代价;时间和代价在最短路径中由一个比例因子控制,通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的,实验结果也表明了该算法的有效性。(2)研究了一类含有必经节点的最短路径问题。该问题有两种类型,一种是有序必经节点的最短路径问题,这一类问题解决的方法是将路径分段,根据前文中的算法求得各个分段节点之间的最短路径,然后再连接在一起即为所求的最短路径;另一类是无序的必经节点最短路径问题。该问题被证明是NP-完全的,本文用汉密尔顿路径算法解决了这一最短路径问题。(3)提出了一种已知到达终点的时间,从而预测源点出发时间的最短路径问题,这可以使驾驶者节约更多的时间,可以较晚的出发,充分利用时间。基于前文改进的最短路径算法通过逆推算的方法得出起始时刻。依据该算法进行求解实验,并对求解结果进行分析,初步验证了该算法的有效性。