b'\n_START_ARTICLE_\nProblema del camino m\xc3\xa1s corto\n_START_PARAGRAPH_\nEn la teor\xc3\xada de grafos, el problema del camino m\xc3\xa1s corto es el problema que consiste en encontrar un camino entre dos v\xc3\xa9rtices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es m\xc3\xadnima. Un ejemplo de esto es encontrar el camino m\xc3\xa1s r\xc3\xa1pido para ir de una ciudad a otra en un mapa. En este caso, los v\xc3\xa9rtices representar\xc3\xadan las ciudades y las aristas las carreteras que las unen, cuya ponderaci\xc3\xb3n viene dada por el tiempo que se emplea en atravesarlas.\n_START_SECTION_\nAnexo: Ejemplo de Algoritmo de Bellman - Ford\n_START_PARAGRAPH_\nOtros algoritmos y evaluaciones asociadas pueden se encontradas en el art\xc3\xadculo de Cherkassky et al.\xe2\x80\x8b\n_START_SECTION_\nGrafos ac\xc3\xadclicos dirigidos\n_START_PARAGRAPH_\nUn algoritmo usando ordenaci\xc3\xb3n topol\xc3\xb3gica puede resolver el problema del camino m\xc3\xa1s corto desde un origen en tiempo lineal, \xce\x98(E + V), en DAG ponderados.\xe2\x80\x8b\n_START_SECTION_\nAlgoritmos para caminos m\xc3\xa1s cortos entre todos los pares de v\xc3\xa9rtices\n_START_PARAGRAPH_\nEl problema del camino m\xc3\xa1s corto entre todos los pares de v\xc3\xa9rtices encuentra los caminos que sean m\xc3\xa1s cortos entre todas las parejas de v\xc3\xa9rtices v, v\' en el grafo. El problema para grafos dirigidos no ponderados fue introducido por Shimbel\xc2\xa0(1953), quien observ\xc3\xb3 que podr\xc3\xada ser resuelto por una serie lineal de multiplicaciones matriciales que toma un tiempo total de O(V\xe2\x81\xb4).\n_START_SECTION_\nAplicaciones\n_START_PARAGRAPH_\nLos algoritmos de los caminos m\xc3\xa1s cortos se aplican para encontrar direcciones de forma autom\xc3\xa1tica entre lugares f\xc3\xadsicos, como las rutas de conducci\xc3\xb3n en sitios de mapas web como MapQuest o Google Maps. Para estas aplicaciones est\xc3\xa1n disponibles r\xc3\xa1pidos algoritmos especializados.\xe2\x80\x8b_NEWLINE_Si un algoritmo representa una m\xc3\xa1quina abstracta no determinista como un grafo, donde los v\xc3\xa9rtices describen estados, y las aristas posibles transiciones, el algoritmo del camino m\xc3\xa1s cortos puede ser usado para encontrar una secuencia \xc3\xb3ptima de decisiones para llegar a un cierto estado final o para establecer l\xc3\xadmites m\xc3\xa1s bajos en el tiempo necesario para alcanzar un estado dado. Por ejemplo, si los v\xc3\xa9rtices 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\xc3\xa1s corto se pueden usar para encontrar la soluci\xc3\xb3n que utiliza el menor n\xc3\xbamero posible de movimientos._NEWLINE_En el argot de las telecomunicaciones, a este algoritmo es tambi\xc3\xa9n conocido como el problema del m\xc3\xadnimo retraso, y con frecuencia va ligado con el problema del camino m\xc3\xa1s ancho. Por ejemplo, el algoritmo podr\xc3\xada buscar el camino m\xc3\xa1s corto entre los m\xc3\xa1s anchos, o el camino m\xc3\xa1s ancho entre los m\xc3\xa1s cortos._NEWLINE_Una aplicaci\xc3\xb3n m\xc3\xa1s coloquial es la teor\xc3\xada de los "Seis grados de separaci\xc3\xb3n", a partir de la cual se intenta encontrar el camino m\xc3\xa1s corto entre dos personas cualesquiera._NEWLINE_Otras aplicaciones incluyen la investigaci\xc3\xb3n de operaciones, instalaciones y facilidad de dise\xc3\xb1o, rob\xc3\xb3tica, transporte y el dise\xc3\xb1o VLSI.\n_START_SECTION_\nProblemas relacionados\n_START_PARAGRAPH_\nEn la geometr\xc3\xada computacional, el problema del camino euclidiano m\xc3\xa1s corto, en el cual dados un conjunto de obst\xc3\xa1culos poli\xc3\xa9dricos en un espacio eucl\xc3\xaddeo y dos puntos, trata de encontrar el camino m\xc3\xa1s corto entre los puntos tal que no se interseca con ninguno de los obst\xc3\xa1culos._NEWLINE_El problema de viajante de comercio, es el problema que trata de encontrar el camino m\xc3\xa1s corto que pasa s\xc3\xb3lo una vez por cada v\xc3\xa9rtice y regresa al comienzo. A diferencia del problema del camino m\xc3\xa1s corto, el cual puede ser resuelto en un tiempo polinomial en grafos sin ciclos negativos, este problema es NP-completo, y como tal, no tiene una resoluci\xc3\xb3n eficiente (ver Clases de complejidad P y NP). El problema de encontrar el camino m\xc3\xa1s largo tambi\xc3\xa9n es NP-completo._NEWLINE_El problema del viajero canadiense y el problema del camino estoc\xc3\xa1stico m\xc3\xa1s corto son generalizaciones donde el grafo no es completamente conocido por el viajero, cambia con el tiempo, o donde los recorridos son probabilisticos.'