En este documento revisamos muchos de los algoritmos conocidos para resolver el problema de la ruta más corta en grafos ponderados por aristas. Luego nos enfocamos en una variante de este problema en la que se incurre en penalizaciones adicionales en los vértices. Estas penalizaciones se pueden utilizar para modelar cosas como tiempos de espera en cruces de carreteras y retrasos debido a trasbordos en el transporte público. La forma habitual de manejar tales penalizaciones es a través de la expansión del grafo. Como alternativa, proponemos dos variantes del algoritmo de Dijkstra que operan en el grafo original, no expandido. Luego se presentan análisis para evaluar las ventajas y desventajas relativas de estos métodos. Asintóticamente, en comparación con el uso del algoritmo de Dijkstra en grafos expandidos, nuestra primera variante es más rápida para grafos muy dispersos pero más lenta con grafos densos. En contraste, la segunda variante presenta tiempos de ejecución en el peor caso idénticos.