propan


“RELATORIA 2”

MODELACION DE GRAFO CAMINO DE COLORES

HOMLET JOHAO PRADA ROMAÑA

TEORIA DE GRAFOS

DOCENTE
MANUEL ALEXANDER VALBUENA HENAO
GRUPO 251


FUNDACION UNIVERSITARIA MARÍACANO
FACULTAD INGENIERIA
INGENIERIA DE SISTEMAS MEDELLIN
MARZO 2014



Texto:
En la teoría de grafos, el problema de los caminos más cortos es el problema que se fundamenta en encontrar uncamino entre dos vértices o nodos de la forma tal que la suma de los pesos de las aristas que lo forman sea la mínima.
Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en unmapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.
Los algoritmos másimportantes 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 deBellman - 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 entreun 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 deJohnson, 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.
Teoría perturbacional, encuentra en el peor delos casos el camino más corto a nivel local.

Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre localizaciones físicas, tales como direccionesen mapas callejeros.
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 de los...