Paso mas corto desde un inicio unico

Paso mas corto desde un inicio unico

José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona

En la teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) en un gráfico de tal manera que la suma de los pesos de sus bordes constituyentes se minimiza.

El problema de encontrar el camino más corto entre dos intersecciones en un mapa de ruta puede ser modelado como un caso especial del problema del camino más corto en los gráficos, donde los vértices corresponden a las intersecciones y los bordes corresponden a los segmentos de carretera, cada uno ponderado por la longitud de la segmento.

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.

El problema del camino más corto puede ser definido para grafos no dirigidos, dirigidos o mixtos. La siguiente es una definición para grafos no dirigidos, en el caso de grafos dirigidos la definición de camino requiere que los vértices adyacentes estén conectados por una apropiada arista dirigida.

Dos vértices son adyacentes cuando poseen una arista común. Un camino en un grafo no dirigido es una secuencia de vértices ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V}$ tal que todo vértice ${\displaystyle v_{i}}$ es adyacente con el vértice ${\displaystyle v_{i+1}}$. Un camino ${\displaystyle P}$ se dice que es de longitud ${\displaystyle n}$ si va desde ${\displaystyle v_{1}}$ hasta ${\displaystyle v_{n}}$.

Sea ${\displaystyle e_{i,j}}$ la arista incidente con los vértices ${\displaystyle v_{i}}$ y ${\displaystyle v_{j}}$. Dada una función de variable real ponderada ${\displaystyle f:E\rightarrow \mathbb {R} }$ y un grafo no dirigido ${\displaystyle G}$, el camino más corto desde ${\displaystyle v}$ hasta ${\displaystyle v'}$ es el camino ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$ (donde ${\displaystyle v_{1}=v}$ y ${\displaystyle v_{n}=v'}$) sobre todos los posibles ${\displaystyle n}$ que minimiza la suma ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$ Cuando cada arista en el grafo tiene un peso unitario o ${\displaystyle f:E\rightarrow \{1\}}$, hallar el camino más corto es equivalente a encontrar el camino con menor número de aristas.

El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de las siguientes generalizaciones:

• El problema de los caminos más cortos desde un origen, en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.
• El problema de los caminos más cortos con un destino, en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.
• El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

Algoritmos

Los algoritmos más importantes para resolver este problema son:

• Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos desde un único vértice origen hasta todos los otros vértices del grafo.
• Algoritmo de Bellman - Ford, resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa.
• Algoritmo de Búsqueda A*, resuelve el problema de los caminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda.
• Algoritmo de Floyd - Warshall, resuelve el problema de los caminos más cortos entre todos los vértices.
• Algoritmo de Johnson, resuelve el problema de los caminos más cortos entre todos los vértices y puede ser más rápido que el de Floyd-Warshall en grafos de baja densidad.
• Algoritmo de Viterbi, resuelve el problema del camino estocástico más corto con un peso probabilístico adicional en cada vértice.

Usos

Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre lugares físicos, como las rutas de conducción en sitios de mapas web como MapQuest o Google Maps. Para estas aplicaciones están disponibles rápidos algoritmos especializados.8​

Si un algoritmo representa una máquina abstracta no determinista como un grafo, donde los vértices describen estados, y las aristas posibles transiciones, el algoritmo del camino más cortos puede ser usado para encontrar una secuencia óptima de decisiones para llegar a un cierto estado final o para establecer límites más bajos en el tiempo necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un puzzle como el Cubo de Rubik y cada arista dirigida corresponde a un simple movimiento o giro, los algoritmos del camino más corto se pueden usar para encontrar la solución que utiliza el menor número posible de movimientos.

En el argot de las telecomunicaciones, a este algoritmo es también conocido como el problema del mínimo retraso, y con frecuencia va ligado con el problema del camino más ancho. Por ejemplo, el algoritmo podría buscar el camino más corto entre los más anchos, o el camino más ancho entre los más cortos.

Una aplicación más coloquial es la teoría de los "Seis grados de separación", a partir de la cual se intenta encontrar el camino más corto entre dos personas cualesquiera.

Otras aplicaciones incluyen la investigación de operaciones, instalaciones y facilidad de diseño, robótica, transporte y el diseño VLSI.