Algoritmos grafos

| 2011 |
| Universidad Católica del Uruguay Dámaso Antonio Larrañaga
Diego Bermúdez – Rodrigo Bermúdez – Filip Szolno
|

[Primera entrega obligatoria] |
|

Teoría de la Computación ylos Sistemas Formales

Dijkstra
Para un origen (vértice del grafo) el algoritmo busca el camino de menor costo entre ese vértice y cada uno de los otros vértices del grafo.
Proceso:
1) Recorrerun vector de tamaño N(cantidad de vértices del grafo) que representa las distancias de el origen a todos los vértices, para poner las distancias en infinito.
2) Se comienza por el vértice origeny se recorre todos los vértices adyacentes excepto los marcados.
3) Si la distancia desde el origen hasta el vértice adyacente es mayor que la distancia desde el origen hasta el vértice actual masla distancia del vértice actual hasta el adyacente, entonces se actualiza la distancia en el vector que representa las distancias.
4) Se marca como visitado el vértice actual.
5) Se repite elpaso 2 con el vértice no marcado como visitado que tenga menor valor en el vector que representa las distancias hasta que se encuentren todos los vértices como visitados.
Para ésta especulaciónsuponemos que los accesos a las posiciones del vector que representa las distancias, el marcar un vértice como visitado o el calcular la distancia del vértice actual a uno de sus adyacentes son de O(1);que la cantidad de vértices del grafo es N y la cantidad de aristas M.
En un grafo conexo o tendiendo a conexo (donde la cantidad de aristas es elevada), cada nodo tiene un número muy alto de nodosadyacentes lo que hace que el algoritmo se comporte con un orden de ejecución de N2. Esto es porque para cada nodo se recorrerán todos los nodos adyacentes no visitados (si el grafo es conexo y todoslos nodos están conectados con todos los demás: N-1 en la primer ejecución, N-2 en la segunda y así sucesivamente).
En un grafo disperso o tendiendo a disperso (donde la cantidad de aristas es...