Problema del camino más corto
- Problema del camino más corto
-
Problema del camino más corto
En teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de sus aristas sea mínima. Una arista es el segmento que une dos nodos y el peso de una arista es el número por el que se pondera tal arista. Un ejemplo es encontrar la forma más rápida de llegar de un lugar a otro en una hoja de ruta. En este caso, los vértices representan los lugares y las aristas representan los segmentos de la carretera, que se ponderan por el tiempo necesario para realizar por el segmento el viaje.
Formalmente el enunciado es: dado un grafo ponderado (es decir, un conjunto V de vértices, un conjunto E de aristas, y una función f: E → R, en la que la imagen de cada arista es un número real que es su peso) y dos vértices v y v', encuéntrese el camino p de v a v´ de tal manera que la cantidad
sea mínima.
El problema es también llamado a veces el problema del único camino par más corto.
Categoría: Teoría de grafos
Wikimedia foundation.
2010.
Mira otros diccionarios:
Problema del camino más largo — Saltar a navegación, búsqueda En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en… … Wikipedia Español
Problema de los caminos más cortos — Saltar a navegación, búsqueda Ejemplo de Grafo Ponderado En la Teoría de grafos, 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… … Wikipedia Español
Algoritmo del vecino mas próximo — El algoritmo del vecino más próximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no … Wikipedia Español
Problema de decisión — Saltar a navegación, búsqueda En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas… … Wikipedia Español
Implementación del algoritmo de Floyd en Java — Saltar a navegación, búsqueda El algoritmo de Floyd intenta resolver el problema de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es similar a construir una tabla con todas las distancias mínimas entre… … Wikipedia Español
Experimento del Mundo Pequeño — Saltar a navegación, búsqueda El experimento del mundo pequeño comprende varios experimentos llevados a cabo por el psicólogo social Stanley Milgram, en su investigación sobre las redes sociales en los Estados Unidos. Lo innovador de esta… … Wikipedia Español
Estado del bienestar — Para otro concepto similar pero diferenciado en su origen y uso en la bibliografía, véase Estado social. Estado del bienestar o Estado providencia (en inglés welfare state) es un concepto de las ciencias políticas y económicas con el que se… … Wikipedia Español
Guerra del Agua (Bolivia) — Saltar a navegación, búsqueda La guerra del Agua de Cochabamba es el nombre popular de una serie de protestas que ocurrieron en Cochabamba, la tercera ciudad más grande de Bolivia, entre enero y abril de 2000. Su detonante fue la privatización… … Wikipedia Español
Guerra del Chaco — Teatro de operaciones militares entre Bolivia y el Paraguay Fecha Septiembre de 1932 a junio de 1935 … Wikipedia Español
Historia del Canal de Panamá — Las esclusas de Miralfores en 2004 La historia del Canal de Panamá se remonta a los primeros exploradores de las Américas. El estrecho puente de tierra entre Norte y Sur América ofrecía una oportunidad única para crear una vía acuática entre los… … Wikipedia Español
