algoritmo de Dijkstra

_angie_
15 de Diciembre del 2008
Socorro, necesito ayuda urgente, ¿alguien puede explicarme cómo funciona este algoritmo? ¿y dónde puedo encontrar implementación de éste en Java?
Muchas gracias.

Havel
15 de Diciembre del 2008
El algoritmo de Dijkstra intenta hallar la manera más rápida de recorrer todos los nodos de un grafo. Para ello se analiza cada una de las componentes conexas por separado.

La idea consiste en tomar siempre de entre los vértices adyacentes al subgrafo seleccionado el más cercano.

Te pongo un ejemplo sencillo:

A ---6---- B----8-------C
|3 ------4 |3
D----2-----E ----F

Supón este grafo.
Tomamos como subgrafo el vértice A y entonces añadimos al subgrafo de entre los vértices adyacentes el más cercano:
Los adyacentes son B y D, luego tomo D y anoto la distancia que llevamos recorrida.

A ---- D Distancia: 3

En el siguiente paso, nuestro subgrafo es A-D y miramos los adyacentes; en este caso B y E. Bueno, pues añadimos el más cercano y actualizamos el camino recorrido:

A----D----E Distancia: 5

Ahora el subgrafo analizado es A-D-E. Miramos los vértices adyacentes: B.

Lo añadimos: A---D---E---B Distancia: 11

Así sucesivamente hasta tener tomados en el subgrafo todos los vértices.

Espero haber conseguido eliminar tus dudas sobre el algoritmo. Siento desconocer dónde encontrar implementaciones del mismo.

Eduardo Avila
15 de Diciembre del 2008
Visita las paginas
http://www.cs.umd.edu/~shankar/417-F01/Slides/chapter4a-aus/sld023.htm
y www.javaboutique.com

Jaqueline
15 de Diciembre del 2008
Saludos
Es posible que me pueda facilitar el pseudocodigo considero muy interesante conocer caminos que me faciliten la optimizacion o minimización de recursos o medios .Gracias

atte Jaqueline Chaves

txuxo
15 de Diciembre del 2008
PSEUDOCODIGO
-------------------------------------------------------------
Entrada: G = (V,E,d), u, v pertenecientes a V

L(u) = 0
L(x) = infinito para cada x distinto de u
T = vacio
mientras v no pertenezca a T hacer
x = a siendo a un vértice que no esté en T con L(a) mínimo
T = T + {x}
for z que no pertenezcan a T
si L(x) + d({x,z}) < L(z) entonces
L(y) = L(x) + d({x,z})
f(z) = x

Salida: L(v) es la longitud del camino mínimo
(v,f(v),f(f(v)),...,u) es el camino mínimo de v a u

------------------------------------------------------------

NOTA: G = (V,E,d). G es el Grafo
V = Vértices (Nodos)
E = Aristas (conexion entre nodos)
d = Peso de cada arista


david
15 de Diciembre del 2008
http://ict.udlap.mx/people/roberto/dijkstra/index.html ahi esta todo