時間依存最短路問題は，有向グラフ G，各辺 e=(v w)における非負な通過時間関数 ce(t)（但し t は v の出る時刻），始点 s，終点 d と出発時刻 t0 が与えられたときに，時刻 t0 に s から出発し d に到着するまでの最も速い経路を計算することで定式化され，古典的な最短路問題（ce 定数）の一般化となっている．この問題に対し，Dijkstra 法の拡張版（Dreyfus '69）が提案されて以来，約 40 年間にわたる研究にも関わらず目覚ましい方法が知られなかったが，本論文は新たに一般化Ａ*アルゴリズムを提案し，さらにその応用として，前処理を用いる ALT アルゴリズム（Goldberg and Harrelson '05）の一般化も与える．Given a directed graph G, a nonnegative transit-time function ce(t) for each edge e=(v,w) (where t is the time to leave v), a source node s, a destination node d and a departure time t0, the time-dependent shortest path problem asks to find an s,t-path that leaves s at time t0 and minimizes the arrival time at d. This formulation generalizes the classical shortest path problem (with constant ce) and can further cover the time-variable case. For near 40 years since the generalized Dijkstra algorithm was proposed (Dreyfus '69), there was no significant advancement despite of many studies. This paper presents a fresh generalized A* algorithm and, as an application, gives a generalization of the ALT algorithm (Goldberg and Harrelson '05) too.