Algoritmo de floyd

Algoritmo de Floyd
En informática, el algoritmo de Floyd descrito en 1959 por Robert Floyd, compara todos los posibles caminos a través del grafo entre cada par de vértices indicándonos la distancia, y el recorrido a seguir en una única ejecución.
Grafos
Es un conjunto de nodos unidos por un conjunto de líneas o flechas. Por lo general, los nodos son entes de procesamiento oestructuras que contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entre estos entes.
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y lasaristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Un grafo simple está formado por dos conjuntos:
• Un conjunto V de puntos llamados vértices o nodos. Es la unidad fundamental de la que están formados los grafos.

• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados mediantelíneas o flechas.
Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino que termina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo es llamado tour. El número de aristas en un camino es la longitud del camino.

En un grafo simple entre dos nodos sólo hay un arco.

Multígrafo. Si hay más de un arco
Grafo dirigido o dígrafo. Se utilizanflechas para conectar los nodos y los arcos pueden recorrer en una en una dirección concreta pero no en la contraria, en ese caso los arcos son entonces aristas.
Grafo no dirigido. Es lo contrario al grafo dirigido.
Pseudografo. Si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante.
Cuando las aristas también tienen algún tipo de información asociada(distancia, costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.
Recorrido de Grafos
Cualquier algoritmo de recorrido de grafos consiste básicamente en visitar un nodo del grafo y luego ir visitando los nodos conectados a este. Este principio se aplica recursivamente comenzando desde un nodo inicial cualquiera del grafo.
Lo que diferencia un algoritmo derecorrido de otro es, una vez ubicado en un nodo en particular, la forma en que se visitan los nodos conectados a este. Por supuesto, estos algoritmos pueden ser aplicados en grafos dirigidos o no dirigidos.
Los dos algoritmos “clásicos” de recorrido de grafos son el recorrido en profundidad y en anchura. Precisamente por ser “clásicos” han sido estudiados con anterioridad y se les conoce suorden de complejidad en tiempo y todos los beneficios de aplicarlos.
Recorrido en profundidad. Para efectuar un recorrido en profundidad de un grafo, se selecciona cualquier nodo como punto de partida (por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como “no visitados”. El nodo inicial se marca como “visitado” y si hay un nodo adyacente a este que no haya sido“visitado”, se toma este nodo como nuevo punto de partida del recorrido. El recorrido culmina cuando todos los nodos hayan sido visitados.
Se dice que el recorrido es en profundidad, porque para visitar otro nodo adyacente del nodo inicial, primero se deben visitar TODOS los nodos adyacentes al que se eligió antes. Es así, como el número de ambientes recursivos varía dependiendo de la profundidadque alcance el algoritmo.
Este algoritmo, recorre todos los nodos del grafo pero fácilmente puede modificarse para que sea una función que encuentre un nodo en particular dentro de grafo.
Una bondad de este algoritmo es que los nodos solo se vistan una vez. Esto implica que si se salvan en alguna estructura las aristas que se van recorriendo se obtienen un conjunto de aristas de...