Grafos

UNIVERSIDAD CENTROCCIDENTAL LISANDRO ALVARADO
DECANATO DE CIENCIAS Y TECNOLOGÍA
COORDINACIÓN DE POSTGRADO

ALGORITMOS DE GRAFOS

Por:
Hazel Colmenarez



Barquisimeto, 2012.

CAPITULO I

MARCO TEÓRICO

ALGORITMO DE GRAFOS

ALGORITMOS PASO MÁS CORTO DESDE INICIO ÚNICO.
Todo camino en un grafo pesado tiene un peso asociado, el cual es la suma de los
pesos de las aristas delcamino. Esta medida esencial nos permite formular problemas
como el de encontrar el camino con el menor peso entre dos vértices. El tópico de
esta sección es el cálculo de este tipo de camino, donde la longitud del camino no se
mide en base al número de aristas del mismo, sino en base al peso del camino. Con
esto último en mente, definiremos al camino más corto entre dos nodos de un grafopesado, como el camino dirigido que tenga la propiedad de tener el peso mínimo
entre todos los caminos que existan entre dicho par de nodos.
Se pueden plantear tres tipos de problemas:
- Camino más corto origen-destino: Dados dos nodos v y w de un grafo, encontrar el
camino más corto que comience en v y culmine w.
- Camino más corto a partir de un origen: Dado un nodo v de un grafo, encontrar elcamino más corto desde v hasta cada uno de los demás nodos.
- Camino más corto entre cada par de nodos
El primero de estos problemas no es más que un caso particular del segundo. En lo
que respecta al segundo, por lo general lo que se busca es tratar de obtener un árbol
de caminos más cortos o el SPT (shortest-path tree), que consiste en un árbol dirigido
que tiene como raíz al nodo origen ytodo camino en el árbol en un camino corto en el
grafo. El tercero de los problemas se puede resolver obteniendo los SPT
correspondientes a cada uno de los nodos del grafo.
1. Algoritmo de Dijkstra
El algoritmo de Dijkstra resuelve el problema de encontrar los caminos más cortos
a partir de un vértice origen al resto de vértices en un grafo, en grafos pesados que no
tengan pesos negativos.También llamado algoritmo de caminos mínimos. Su
nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos
más cortos que parten del vértice origen y que llevan a todos los demás vértices;
cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que
componen elgrafo, el algoritmo se detiene. El algoritmo es una especialización de la
búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo
negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de
la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al
pasar por una arista con costo negativo).
Pasos del Algoritmo.
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo
inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x
al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son
desconocidas al principio, exceptuando la de x que se debe colocar en 0
debido a que la distancia de x a x sería 0.
2. Sea a =x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados,
llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde
x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la
segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5. Marcamos como completoel nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse
almacenando los valores en una cola de prioridad) y volvemos al paso 3
mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
El algoritmo de Dijkstra es un algoritmo voraz que opera a partir de un conjunto S
de nodos cuya distancia más corta desde el origen ya...