Estoy buscando una implementación Java genérica del algoritmo de Dijkstra. He intentado codificar esto por mi cuenta, pero sigo teniendo problemas. Si ayuda, sé de hecho que el gráfico siempre está conectado. ¿Alguien sabe de tal implementación?¿Dónde puedo obtener una implementación de Java del algoritmo de Dijkstra?
Gracias!
Esto es totalmente desvergonzado, pero codifiqué una implementación del algoritmo de Dijkstra usando montones de Fibonacci hace un tiempo y lo publiqué en mi sitio web personal. Puede encontrar el código aquí:
He tratado de comentar el código para indicar cómo funciona el algoritmo, qué supuestos se trata de hacer, etc., así que espero que es Fácil de leer y entender. Avíseme si hay algo al respecto que pueda aclararle.
Espero que esto ayude!
Qué quiere decir esto:
(la aplicación Java se puede encontrar en enlace mencionado (véase la parte inferior de esta respuesta)
// initialize d to infinity, π and Q to empty
d = (∞)
π =()
S = Q =()
add s to Q
d(s) = 0
while Q is not empty
{
u = extract-minimum(Q)
add u to S
relax-neighbors(u)
}
relax-neighbors(u)
{
for each vertex v adjacent to u, v not in S
{
if d(v) > d(u) + [u,v] // a shorter distance exists
{
d(v) = d(u) + [u,v]
π(v) = u
add v to Q
}
}
}
extract-minimum(Q)
{
find the smallest (as defined by d) vertex in Q
remove it from Q and return it
}
edición: conseguido esto desde http://renaud.waldura.com/doc/java/dijkstra/
Eso no está compilando en mi versión de java. ¿Qué versión estás usando? – Patrick87
Creo que el OP busca específicamente el código de Java en lugar de pseudocódigo; la pregunta sugiere que el OP ha encontrado pseudocódigo pero tiene problemas para traducirlo a Java. – templatetypedef
la implementación de Java se puede encontrar en el enlace :) –
JGrapht es una biblioteca común de Java para gráficos. También se implementa el algoritmo de dijkstra.
Buenos recursos de Universidades
la Universidad de Nueva York en http://www.cs.nyu.edu/~vs667/development/~DijkstraAlgorithm/
De Princeton University en http://algs4.cs.princeton.edu/41undirected/Graph.java.html
también vogella hizo una buena aplicación a http://www.vogella.com/articles/JavaAlgorithmsDijkstra/article.html
que necesitaba para la sencilla sin dirección gráfico conectado s :) – MozenRath
@ Piyush: puede representar un gráfico no dirigido utilizando un gráfico dirigido: simplemente haga que cada par de nodos conectados apunten entre sí. – templatetypedef
@templatetypedef En mi opinión, su código es el más limpio que he visto en la red para dijkstra, ¿podría compartir también el enlace de DirectedGraph que pasa como argumento? – JavaDeveloper