Ejemplo en cartografía

Para estudiar los distintos algoritmos, vamos a interesarnos en un pequeño juego en el que controlamos a un personaje que representa un explorador. Como en muchos juegos de rol, nuestro héroe está limitado en cada turno (no tiene derecho más que a cierto número de puntos de acción). Para ir lo más rápido posible desde un punto a otro, buscaremos la ruta más corta en el mapa, teniendo en cuenta el tipo de terreno.

Existen varias formas, que requieren más o menos energía (y por consiguiente, puntos de acción):

El mapa es el siguiente:

Y la leyenda:

Vamos a buscar la ruta que permita ir desde el punto de partida (P) hasta el destino (D), utilizando la menor cantidad posible de puntos de acción. La ruta más corta cuesta 27 puntos de acción (siguiendo la ruta y pasando el primer puente; a continuación, acortando por hierba hasta el final).