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

\sum_{p\ } f(p)

sea mínima.

El problema es también llamado a veces el problema del único camino par más corto.

Obtenido de "Problema del camino m%C3%A1s corto"

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

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”