aefresdatfgews


UNIVERSIDAD TECNOLÓGICA NACIONAL





Materia: Algoritmos Complejos y Estructuras Complejas de Datos

Curso: K3051

Docente: Pablo A. Sznajdleder

Tema de investigación: Algoritmo de Dijkstra




Apellido y Nombre
Numero de Legajo
Croce Agustin
143.356-8
Hamie, Lucas

Tamburro, Fernando Gabriel
140.703-0
Relañez, Alejandro142.070-7
Milar, Tomás
143.409-3

















Indice


1. Indice . ………………………………………………………………………………....Pag. 2
2. Nociones previas sobre grafos ……………………………………………………..Pag. 3
3. Introducción ………………………………………………..………………………….Pag. 3
4. Estrategia del algoritmo ……………………………..……………………………….Pag. 4
5. Complejidad …….……………………………..………………………………………Pag. 5
6. Casos de uso oaplicaciones prácticas …………………………………………….Pag. 9
7. Conclusión……………………………………………………………………………..Pag. 10
8. Fuentes…………………………………………….…………………………………..Pag. 10




Nociones previas sobre grafos

Grafo: Conjunto de vértices o nodos unido por aristas o arcos con el fin de representar las relaciones binarias entre los elementos del mismo.

Vértice: Unidad fundamental e indivisible de un grafo. Deestos parten y llegan las aristas

Arista: Relación entre dos vértices de un grafo sin dirección.

Arista Dirigida: Arista la cual también contiene una direccion.

Arista Ponderada: Arista que tiene asociado un peso.

Vértice adyacente: Un vértice a es adyacente al vértice b si existe una arista que parte de a y llega a b.

Grafo Dirigido: Grafo donde todas sus aristas son dirigidas.Grafo Ponderado: Grafo donde todas las aristas son ponderadas.

Camino de X a Y: Conjunto de aristas que conectan los vértices X e Y.




Introduccion.

El algoritmo de Dijkstra, también conocido como el algoritmo del camino mínimo fue creado en 1950 por el holandés Edsger Wybe Dijkstra. Entre los otros aportes de Dijkstra a la computación se destaca la notación polaca inversa, el algoritmodel banquero y la estructura del semáforo para coordinar el uso de recursos compartidos entre diferentes procesos.

Este algoritmo resuelve el problema del camino más corto, es decir, encontrar en un grafo dirigido ponderado el camino entre dos vértices tal que la suma del peso de sus aristas sea mínima.












Estrategia del algoritmo

Paso #1: Se marcan todos losvértices como no visitados.

Paso #2: Se establece la distancia del vértice inicial como cero y la del resto de los vértices como infinita.

Paso #3: Se establece como vértice actual el nodo inicial.

Paso #4: Por cada vértice no visitado adyacente al vértice actual se establece como la nueva
distancia al mínimo entre la distancia actual y la suma de la distancia del vértice actual más el peso dela arista que conecta ambos vértices.

Paso #5: Se marca el vértice actual como visitado.

Paso #6: Si el nodo destino ha sido marcado el algoritmo es finalizado siendo la distancia del camino mínimo la distancia del nodo destino. En caso de que el nodo marcado no sea el nodo destino se elige como nodo actual al nodo no visitado con la menor distancia y se vuelve a #4.

Versión con colade prioridad

Las colas con prioridad (y por tanto la estructura de datos montículo con la que se representan en memoria) se utilizan a menudo para mejorar la eficiencia de algoritmos en los que iterativamente se precisa conocer el mínimo (o máximo) de un conjunto de valores y eliminarlo del conjunto.

1 método Dijkstra(Grafo,origen):
2 creamos una cola de prioridad Q
3 agregamos origena la cola de prioridad Q
4 mientras Q no este vacío:
5 sacamos un elemento de la cola Q llamado u
6 si u ya fue visitado continuo sacando elementos de Q
7 marcamos como visitado u
8 para cada vértice v adyacente a u en el Grafo:
9 sea w el peso entre vértices ( u , v )
10 si v no ha sido visitado:
11 Relajacion( u , v , w )...