Los algoritmos eficientes de caminos más cortos son de clave importancia para los sistemas de enrutamiento y navegación. Sin embargo, estas aplicaciones están diseñadas enfocándose en los requisitos de los vehículos de motor, y por lo tanto, encontrar caminos en secciones peatonales de áreas urbanas no está suficientemente soportado. Además, encontrar el camino más corto a menudo no es adecuado para las rutas de aceras urbanas, ya que los usuarios de estas aplicaciones también pueden estar interesados en rutas alternativas que, aunque ligeramente más largas, poseen otras características y propiedades deseables. Según la literatura, la búsqueda de rutas alternativas se lleva a cabo principalmente utilizando el algoritmo de k-caminos más cortos (KSP) que representa una lista ordenada de todas las alternativas disponibles. A pesar de que se han propuesto varios algoritmos KSP, hasta donde sabemos, no hay investigaciones que aborden todos los problemas inherentes a un sistema de navegación peatonal. El propósito de este artículo es presentar un algoritmo heurístico para conjuntos de datos de grafos que implementa un método basado en penalizaciones que, al aumentar ciertos pesos de los bordes, busca efectivamente los caminos alternativos más accesibles en casos de múltiples rutas. Para demostrar cómo funciona el algoritmo, presentamos resultados experimentales sobre la búsqueda de los caminos más accesibles en secciones peatonales del centro histórico de la ciudad de Tesalónica.