Camino minimo - grafos
-
-
-
- 2,744
- mensajes
-
- miembro desde
- 15/07/05
Buenas gente, queria compartir con ustedes el codigo fuente en Java de uno de los algoritmos de grafos para hallar caminos minimos, tiene una implementacion propia de un grafo como una lista de vertices y una lista de aristas y la implementacion del algoritmo Bellman - Ford para caminos minimos que puede ser usado en grafos dirigidos y con peso negativo en sus aristas.
El codigo es bastante sencillo de seguir y extensible a otros algoritmos mas como el de dijkstra...
El codigo viene con una clase main que genera un grafo basico y luego por cada vertice dentro del grafo computa la distancia minima al resto de los vertices mostrando el camino minimo y la distancia minima...
Espero que les sea de utilidad... -
-
-
-
- 2,744
- mensajes
-
- miembro desde
- 15/07/05
Agrego la implementacion del algoritmo de Dijkstra para caminos minimos. Ahora esta implementado el programa principal usando los dos algoritmos Bellman-Ford y Dijkstra sobre el mismo grafo...
Espero que a alguien le sea util...
Saludos
Pablo -
-
-
-
- 2,744
- mensajes
-
- miembro desde
- 15/07/05
Agrego la implementacion del algoritmo Johnson's para el computo del camino minimo entre todos los pares de vertices del grafo, este algoritmo eta basado en la aplicacion el algoritmo de Bellman-Ford y luego aplicarsele Dijkstra sbore cada uno de los vertices como vertice de origen.
Pueden ver la implementacion...
Espero que les sea util...
Saludos
Pablo -
-
-
-
- 3,705
- mensajes
-
- miembro desde
- 14/10/04
-
-
-
-
- 7,194
- mensajes
-
- miembro desde
- 27/11/07
-
-
-
-
- 2,744
- mensajes
-
- miembro desde
- 15/07/05
No encontre muchas diferencias yo, el tema que el algoritmo de Floyd - Warshall trabaja sobre una matriz de pesos / distancias iniciales y mediante programacion dinamica va en un orden de O (n^3) calculando todas las distancias minimas entre todos los vertices...Escrito por Kryptonyte
El algoritmo de Johnsons toma un approach diferente, lo que primero hace es agregar un vertice mas "Q" al grafo y lo conecta con todos los demas nodos mediante aristas de peso 0, luego aplica Bellman-Ford al grafo tomando como nodo inicial a ese vertice "Q", y luego hace una renormalizacion de los pesos / distancias de cada nodo para remover los "pesos negativos", una vez que este proceso termina, se remueve el nodo "Q" del grafo y todas las aristas que conectaban este nodo con el resto, y sobre este grafo ahora se realiza Dijkstra tantas veces como nodos tenga en el grafo, al finalizar obtengo la distancia minima entre cada par de vertices...
Es un algoritmo sencillo de implementar una vez que tenes implementado Bellman-Ford y Dijkstra...
Saludos
Pablo -
-
-
-
- 7,194
- mensajes
-
- miembro desde
- 27/11/07
Te lo digo porque el algoritmo de Floyd se reduce a:
procedure FloydWarshall ()
for k := 1 to n
for i := 1 to n
for j := 1 to n
path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
y es O(n^3), lo mismo que el algoritmo de Johnson, tal como lo presentás. Incluso parece más simple aplicar Dijkstra para todos los nodos tomados como origen.
Así que, como el algoritmo de Floyd es de épocas remotas (en términos de computación), alguna ventaja debería tener el de Johnson. -
-
-
-
- 1
- mensajes
-
- miembro desde
- 19/06/09
-
-
-
-
- 1
- mensajes
-
- miembro desde
- 07/10/11
-
-
-
-
- 1
- mensajes
-
- miembro desde
- 04/06/09
-
