grafos 8.6.1
Post on 14-Apr-2017
348 Views
Preview:
TRANSCRIPT
Sección 8.6Caminos de Longitud Mínima
Tomado de Matemáticas Discretas y sus Aplicaciones. Rosen Esteban Andrés Díaz Mina
Introducción
Muchos problemas se pueden representar utilizando grafos en los que se le asigna un peso a cada una de las aristas. Por ejemplo, la forma en que se representa el sistema de vuelos de una línea aérea. Se construye un sistema básico donde las ciudades están representadas por los vértices y los vuelos por las aristas. Los problemas relacionados por las distancias se pueden representar asignándoles a las aristas las distancias entre ciudades.
Introducción
Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Los grafos ponderados se utilizan para representar redes informáticas y pueden emplearse para estudiar los costos de comunicación, los tiempos de respuesta de los ordenadores o la distancia entre ordenadores.
Introducción
Hay diversos problemas relacionados con los grafos ponderados que aparecen con frecuencia. Uno de ellos es el de determinar un camino de longitud mínima entre los vértices de una red. Más concretamente, se define la longitud de un camino en un grafo ponderado como la suma de los pesos de las aristas de ese camino . La pregunta es: ¿Cuál es el camino más corto, esto es, el camino de longitud mínima, entre dos vértices dados?
Grafo Ponderado - Distancia
Grafo Ponderado – Tiempo de Vuelo
El problema del Camino de Longitud Mínima
Existen diferentes algoritmos para hallar un camino de longitud mínima entre dos vértices de un grafo ponderado. Se presenta un algoritmo desarrollado por el matemático holandés Edsger Dijkstra en 1959. La versión que se describe resuelve este problema para grafos ponderados no dirigidos si todos los pesos son positivos.
Teorema 1
El algoritmo de Dijkstra determina la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido.
Algoritmo de Dijkstra
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Ejemplo
Ejemplo
FinalizamosCaminos de Longitud Mínima
Hasta pronto
top related