5.3.1 El camino mas corto

5.3.1 El camino más corto

El problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

En la teoría de grafos, el problema del camino más corto es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo de esto es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representarían las ciudades y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. Lo constituyen es mínima.

Ejemplo:

Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino: 

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visited 

Nota: En este ejemplo se utiliza una coma como separador decimal

SAUCEDO, F. E. (s.f.). Matematicas Discretas. Obtenido de Matematicas Discretas: https://sites.google.com/site/matedicreta/6-3-1-el-camino-mas-corto