Problema del camino más corto
En la teoría de grafos , el problema de la ruta más corta es el problema de encontrar una ruta entre dos vértices (o nodos) en un gráfico de manera que se minimice la suma de los pesos de sus aristas constituyentes.
El problema de encontrar la ruta más corta entre dos intersecciones en un mapa de carreteras puede modelarse como un caso especial del problema de la ruta más corta en los gráficos, donde los vértices corresponden a las intersecciones y los bordes corresponden a los segmentos de la carretera, cada uno ponderado por la longitud de la ruta. segmento.
El problema del camino más corto se puede definir para gráficos si no dirigida , dirigida , o mezclado . Se define aquí para gráficos no dirigidos; para grafos dirigidos, la definición de trayectoria requiere que los vértices consecutivos estén conectados por un borde dirigido apropiado.
Dos vértices son adyacentes cuando ambos inciden en un borde común. Un camino en un grafo no dirigido es una secuencia de vértices de tal manera que es adyacente a para . Este camino se llama camino de longitud de a . (Las son variables; su numeración aquí se relaciona con su posición en la secuencia y no necesita relacionarse con ningún etiquetado canónico de los vértices).
