Shortest path problein with cache dependent path lengths
Zhaohui Fu, Andika Eka Kurnia, Andrew E. B. Lim, Brian B. Rodrigues · 2004
Here, we are motivated by the problem of finding the shortest path in a network when traversing Web pages where cache size determines path length. The shortest path problem with cache-dependent path lengths is shown to be NP-complete. It is a new problem for which we propose several effective heuristics, including a Dijkstra heuristic, genetic algorithms and tabu search.