We consider two time-dependent adaptations of the n-ANT algorithm: Attiratanusanthron and Fakcharoenphol’s (2008) n-ANT algorithm with time-dependent evaporation rate (n-ANT/tdev) and n-ANT with time-dependent lower pheromone bound (n-ANT/tdlb). We analyze the running time of both variants on the single destination shortest path problem (SDSP). We show that n-ANT/tdev has a super-polynomial running time on the SDSP. In contrast, we show that n-ANT/tdlb achieves a polynomial running time on this problem. This demonstrates rigorously how these time-dependent adaptions affect the performance of ACO variants, both positively and negatively. Moreover, we show that Gutjahr’s Graph-based Ant System with time-dependent evaporation rate (GBAS/tdev) converges to the optimal solution under a slightly stronger evaporation rate function than was previously known.